কনটেন্টে যান

007 — Dynamic Range Minimum Queries

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

  • Original source: CSES Problem Set — Range Queries section
  • Platform: CSES Problem Set — "Dynamic Range Minimum Queries" — https://cses.fi/problemset/task/1649
  • Topic: segment tree and fenwick tree
  • Difficulty: Medium
  • Pattern: min segment tree (এখানে Fenwick চলবে না)
  • Basic idea inherited from: segment tree generalization

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

n-টা সংখ্যার array, আর q-টা operation দুই রকমের একটা:

উদাহরণ
type 1:  "k u"   ->  index k-এর value u বানাও  (update)
type 2:  "a b"   ->  index a থেকে b পর্যন্ত MINIMUM বলো  (range min)

এটা ঠিক Dynamic Range Sum (#6)-এর মতোই — শুধু "sum"-এর জায়গায় "minimum"। আর এই একটা শব্দ পরিবর্তনই Fenwick tree-কে অকেজো করে দেয়।

Input ও output

উদাহরণ
n = 6, array = [5, 2, 8, 1, 9, 3]
  2 1 3   ->  min a[1..3] = min(5, 2, 8) = 2
  1 4 0   ->  set a[4] = 0   (array: [5, 2, 8, 0, 9, 3])
  2 3 5   ->  min a[3..5] = min(8, 0, 9) = 0
  2 1 6   ->  min a[1..6] = min(5,2,8,0,9,3) = 0

Output:
  2
  0
  0

চেনা উদাহরণে বোঝা

ভাবো একটা পাহাড়ি এলাকার weather-station নেটওয়ার্ক। প্রতিটা ছোট অঞ্চল তার সর্বনিম্ন তাপমাত্রা রাখে, প্রতিটা বড় অঞ্চল তার অধীন ছোট অঞ্চলগুলোর সর্বনিম্ন রাখে। "এই কয়েকটা অঞ্চলের মধ্যে সবচেয়ে কম তাপমাত্রা কত" জিজ্ঞেস করলে কয়েকটা ready সর্বনিম্ন তুলনা করলেই উত্তর। কিন্তু খেয়াল করো — তুমি দুটো অঞ্চলের সর্বনিম্ন "যোগ-বিয়োগ" করে তৃতীয়টা বের করতে পারবে না; min এভাবে কাজ করে না।

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

এটা segment tree generalization-এর উপর দাঁড়িয়ে। ../segment-tree.md section 8-এ দেখা গেছে: tree-র কোনো কিছুই "sum"-এর উপর নির্ভর করে না, শুধু combine step ছাড়া। combine বদলে দিলেই একই tree min/max/gcd করতে পারে।

ভেতরের যুক্তি

লুকানো logic: associativity, কিন্তু invertibility নয়। min associative (min(min(a,b),c) = min(a,min(b,c))), তাই segment tree-তে দিব্যি চলে। কিন্তু min invertible নয় — একটা সংখ্যা "বিয়োগ করে" minimum থেকে সরানো যায় না। ঠিক এ কারণেই Fenwick-এর prefix(r) - prefix(l-1) trick ভেঙে পড়ে।

কী দিয়ে তথ্য রাখব

একটা min segment tree। প্রতিটা node তার segment-এর minimum জমায়; combine হলো min(left, right); "fully outside" হলে identity হলো +infinity (যাতে min-এ কোনো প্রভাব না ফেলে)।

এটি কেন উপযুক্ত

Update + arbitrary range min — দুটোই O(log n) দরকার। Fenwick এখানে অচল কারণ min invertible নয়। Segment tree generalize করে: একই build/query/update কাঠামো, শুধু combine = min আর identity = +inf। একটা leaf O(log n)-টা segment-এ থাকে, query O(log n)-টা segment জোড়ে — তাই দুটোই log n।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

প্রথম সরল চিন্তা: plain array; update মানে a[k]=u (O(1)), range min মানে loop চালিয়ে সবচেয়ে ছোট খোঁজা (O(n))।

উদাহরণ
update: a[k] = u
query : m = +inf; for i in a..b: m = min(m, a[i])

আর prefix-sum-এর মতো "prefix min" রাখলেও update সামলায় না — কারণ min invertible নয়।

কোথায় বেশি কাজ হচ্ছে

প্রতিটা range-min query O(n), q-টা query মিশলে O(n·q) — contest scale-এ TLE। আর prefix-min array update সহ্য করে না: একটা element ছোট থেকে বড় হলে, পরের prefix-min-গুলো আর পুরোনো বিয়োগ করে ঠিক করা যায় না, পুরো rebuild লাগে — তাও O(n)। তাই brute অচল।

যে বিষয়টি খেয়াল করতে হবে

মূল observation: min associative কিন্তু invertible নয় — তাই segment tree চলে, Fenwick চলে না। একই tree কাঠামো, শুধু combine = min আর "outside" identity = +inf। একটা update আগের মতোই এক root-to-leaf path repair করে।

আরও কম কাজে সমাধান

6-এর segment tree নাও, দুটো জিনিস বদলাও: (1) combine + থেকে min, (2) outside-return 0 থেকে float('inf')। build/update/query-এর recursion হুবহু এক থাকে। update leaf set + path re-min; query তিন-ভাগের decision, ready segment-গুলোর min নেয়।

ভাবনার পরিবর্তন

মোচড়: "Fenwick তো sum-এ কাজ করল, min-এও করবে" — এই ফাঁদ এড়াও। আগে জিজ্ঞেস করো "operation-টা কি invertible?"। sum/xor হ্যাঁ (Fenwick চলে); min/max/gcd না (segment tree লাগে)। এই একটা প্রশ্নই structure বেছে নেওয়ার আসল চাবি।

ছবিতে বোঝা

Min segment tree on [5, 2, 8, 1, 9, 3] (প্রতিটা node-এ [range] = stored min):

উদাহরণ
                      [0..5] = 1
                     /          \
            [0..2] = 2          [3..5] = 1
            /       \            /        \
     [0..1] = 2  [2..2] = 8  [3..4] = 1  [5..5] = 3
      /     \                  /     \
[0..0]=5  [1..1]=2      [3..3]=1  [4..4]=9

combine: parent = min(left child, right child)
query(0, 3) = min([0..1]=2, [2..2]=8, [3..3]=1) = 1

ছোট input-এ ধাপে ধাপে

[5, 2, 8, 1, 9, 3], set index 3 = 0 তারপর min [2..4]:

  1. Build: root [0..5] = 1।
  2. update(3, 0): leaf [3..3] = 0; ফেরার পথে [3..4] = min(0,9)=0, [3..5] = min(0,3)=0, root = min(2,0)=0।
  3. query(2, 4): [2..2]=8 (ভেতরে), [3..4]=0 (ভেতরে) → min(8,0)=0।
  4. উত্তর = 0। ✓
  5. কোনো rebuild নেই — শুধু এক শৃঙ্খল re-min, কয়েক টুকরোর min।

কোড ও ব্যাখ্যা

Python

Python
class MinSegmentTree:
    """RANGE MIN + POINT UPDATE। Element নয়, SEGMENT-এর min জমায়।
    sum tree থেকে শুধু দুটো পরিবর্তন:
      combine: min(left, right)   (যোগের বদলে)
      outside identity: +inf      (0-এর বদলে)
    min associative, তাই segment tree-তে চলে; কিন্তু invertible নয়,
    তাই Fenwick-এর prefix-subtraction trick এখানে অচল।"""

    INF = float('inf')

    def __init__(self, data):
        self.n = len(data)
        self.tree = [self.INF] * (4 * self.n)
        if self.n:
            self._build(data, 0, 0, self.n - 1)

    def _build(self, data, node, lo, hi):
        if lo == hi:
            self.tree[node] = data[lo]
            return
        mid = (lo + hi) // 2
        self._build(data, 2 * node + 1, lo, mid)
        self._build(data, 2 * node + 2, mid + 1, hi)
        self.tree[node] = min(self.tree[2 * node + 1], self.tree[2 * node + 2])

    def update(self, i, value):                   # set a[i] = value (0-indexed)
        self._update(0, 0, self.n - 1, i, value)

    def _update(self, node, lo, hi, i, value):
        if lo == hi:
            self.tree[node] = value
            return
        mid = (lo + hi) // 2
        if i <= mid:
            self._update(2 * node + 1, lo, mid, i, value)
        else:
            self._update(2 * node + 2, mid + 1, hi, i, value)
        self.tree[node] = min(self.tree[2 * node + 1], self.tree[2 * node + 2])

    def query(self, l, r):                         # min of [l, r] inclusive
        return self._query(0, 0, self.n - 1, l, r)

    def _query(self, node, lo, hi, l, r):
        if r < lo or hi < l:                       # পুরো বাইরে
            return self.INF                        # min-এর identity
        if l <= lo and hi <= r:                    # পুরো ভেতরে
            return self.tree[node]
        mid = (lo + hi) // 2                        # আংশিক: ভাঙো
        return min(self._query(2 * node + 1, lo, mid, l, r),
                   self._query(2 * node + 2, mid + 1, hi, l, r))


def brute(arr, l, r):
    return min(arr[l:r + 1])


# ---- tests ----
data = [5, 2, 8, 1, 9, 3]
st = MinSegmentTree(data)

assert st.query(0, 2) == 2                    # min(5,2,8)
st.update(3, 0)                               # index 3 -> 0
data[3] = 0
assert st.query(2, 4) == 0                    # min(8,0,9)
assert st.query(0, 5) == 0                    # পুরো array

# update আর query মিশিয়ে, mirror array-র সাথে exhaustively যাচাই
import random
random.seed(13)
arr = [random.randint(-9, 9) for _ in range(18)]
st = MinSegmentTree(arr)
for _ in range(500):
    if random.random() < 0.5:
        i = random.randrange(len(arr))
        v = random.randint(-9, 9)
        arr[i] = v
        st.update(i, v)
    else:
        l = random.randrange(len(arr))
        r = random.randrange(l, len(arr))
        assert st.query(l, r) == brute(arr, l, r)

print("সব test pass!")

কোডের প্রতিটি অংশ

  • INF = float('inf') — min-এর identity; "outside" segment এটা ফেরত দিলে min-এ কোনো প্রভাব পড়ে না।
  • _build / _update-এ combine = min(left, right) (sum tree-র +-এর বদলে)।
  • _query outside হলে INF, inside হলে ready min, আংশিক হলে দুই child-এর min।
  • brute + random fuzz — mirror array-র min(...)-এর সাথে মিলিয়ে দেখা।

Output মিলিয়ে দেখা

MinSegmentTree([5,2,8,1,9,3]): query(0,2)=2। update(3,0)-এর পর query(2,4)=0, query(0,5)=0। তারপর 500 random op fuzz (negative-সহ): প্রতিটা query mirror-এর brute min-এর সাথে মেলে। সব assert pass। শেষে print: সব test pass!।

খরচ ও সাধারণ ভুল

সময়

Build O(n), update O(log n), query O(log n)। মোট O(n + q log n)।

অতিরিক্ত জায়গা

O(n) — size 4n-এর tree array।

যে ভুলগুলো এড়াতে হবে

  • min-এ Fenwick দিয়ে চেষ্টা করা — invertible নয়, তাই arbitrary range-এ ভুল; segment tree লাগবেই।
  • outside identity ভুল করা (0 রেখে দেওয়া) — তখন min সবসময় ≤ 0 হয়ে যাবে; +inf দরকার।
  • update-এর পর parent re-min করতে ভুলে যাওয়া — তাহলে stale min থেকে যায়।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

ভিত্তি: segment tree generalization (../segment-tree.md section 8 — যেকোনো associative combine)। সরাসরি #6 (Dynamic Range Sum)-এর সাথে যমজ, শুধু combine/identity বদলানো। runnable reference ../implementation.py।

পরের অনুশীলন

  • Range Xor Queries (আবার invertible, তাই prefix/Fenwick চলে) — CSES "Range Xor Queries" (এই tracker-এর #8)
  • Hotel Queries (max segment tree বেয়ে নামা — descent trick) — CSES "Hotel Queries" (#15)
  • Range maximum / gcd variants (একই tree, combine বদলানো) — ../segment-tree.md section 8

কৌশলটি মনে রাখুন

Min segment tree: combine = min, identity = +inf — sum tree-র জমজ ভাই। বড় শিক্ষা: structure-choice নির্ভর করে operation invertible কি না তার উপর। sum/xor → Fenwick চলে; min/max/gcd → segment tree লাগে।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: range-min/max/gcd দেখলেই segment tree, কখনো Fenwick নয় — কারণ এরা invertible নয়। sum tree আর min tree-র মধ্যে তফাত মোটে দুই লাইন (combine আর identity)। এই generalization বোঝাটাই segment tree-কে একটা সাধারণ-উদ্দেশ্য range-query engine বানিয়ে তোলে।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।