007 — Dynamic Range Minimum Queries¶

Source¶

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

1. Problem in simple words¶

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-কে অকেজো করে দেয়।

2. Which basic idea does this inherit from?¶

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

3. What is the hidden math or logic?¶

লুকানো 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 ভেঙে পড়ে।

4. Which data structure is needed?¶

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

5. Why this data structure fits¶

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।

6. Real-life analogy¶

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

7. Visual explanation¶

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

8. Example input and 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

9. Brute force thinking¶

প্রথম সরল চিন্তা: 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 নয়।

10. Why brute force is slow¶

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

11. Key observation¶

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

12. Optimized intuition¶

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 নেয়।¶

13. Thinking tweak¶

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

14. Step-by-step dry run¶

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

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

15. Python solution¶

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!")

16. Line-by-line code explanation¶

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(...)-এর সাথে মিলিয়ে দেখা।

17. Output walkthrough¶

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!।

18. Time complexity¶

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

19. Space complexity¶

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

20. Common mistakes¶

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

21. Which basic problem this inherits from¶

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

22. Similar harder problems¶

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

23. Pattern learned¶

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

24. Final summary¶

ভবিষ্যতের আমাকে: 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।