# Segment Tree — শুধু Element নয়, Segment-এর Answer জমাও [অধ্যায়ের সূচি](README.md) · [সহজ ব্যাখ্যা ও বাস্তব ব্যবহার](learning-guide.md) · [অনুশীলন ও সমাধান](problems/README.md) > একটা মাত্র thinking tweak একটা array-কে query machine বানিয়ে দেয়: *interval*-গুলোর answer আগে থেকে হিসেব করে tree-র মতো সাজিয়ে রাখো, তাহলে যে range-ই জিজ্ঞেস করা হোক, সেটা কয়েকটা ready interval-এর union। --- ## 1. ব্যথাটা: update আসা মাত্রই prefix sums ভেঙে পড়ে Prefix sums তুমি আগে থেকেই জানো — [../01-math-based-programming-fundamentals/05-prefix-difference-contribution/](../01-math-based-programming-fundamentals/05-prefix-difference-contribution/README.md) থেকে। জমে থাকা (frozen) array-র জন্য এরা perfect: ```text array = [2, 5, 1, 4, 9, 3] prefix = [0, 2, 7, 8, 12, 21, 24] sum of a[1..4] = prefix[5] - prefix[1] = 21 - 2 = 19 (O(1), beautiful) ``` এবার array-টা বদলালো: `a[2] = 6`, আগে ছিল `1`। Index 3 থেকে শুরু করে প্রতিটা prefix entry এখন ভুল: ```text prefix = [0, 2, 7, 8, 12, 21, 24] ^ ^ ^ ^ all stale — must rebuild, O(n) ``` একটা update-এর খরচ O(n)। 100,000-টা update আর 100,000-টা query মিশে থাকলে হিসেব দাঁড়ায় প্রায় 10^10 operation। Prefix-sum trick-টা query-র সময় বাঁচিয়েছিল *এক বিশাল pre-computation* করে — আর update সেই pre-computation-টাকেই ধ্বংস করে দেয়। **সমাধান pre-computation ছেড়ে দেওয়া নয়। সমাধান হলো সেটাকে এত ছোট ছোট টুকরোয় ভাঙা, যাতে একটা update শুধু কয়েকটা টুকরোকে invalid করে।** ## 2. Thinking tweak: interval-কে অর্ধেক করতে থাকো `[0..5]` range-টা নাও আর অর্ধেক করতে থাকো: ```text [0..5] / \ [0..2] [3..5] / \ / \ [0..1] [2..2] [3..4] [5..5] / \ / \ [0..0] [1..1] [3..3] [4..4] ``` বারবার অর্ধেক করে যত range পাওয়া যায়, প্রতিটাকে বলে **segment**। দুটো fact এই ছবিটাকে শক্তিশালী করে: - মোট segment আছে মাত্র `2n`-টার মতো — জমিয়ে রাখা সস্তা। - **যেকোনো** query range `[l..r]`-কে সর্বোচ্চ O(log n)-টা segment দিয়ে tile করা যায়। (Tree-র প্রতিটা level-এ একটা query সর্বোচ্চ দুটো segment-কে "আংশিকভাবে কাটতে" পারে — দুই প্রান্তে একটা করে — তাই প্রতি level থেকে মোটে ~2-টা node পরের level-এ টিকে থাকে।) তাহলে আমরা প্রতিটা segment-এর জন্য একটা করে pre-computed answer জমাই। একটা update একটা leaf ছোঁয়, আর একটা leaf মাত্র O(log n)-টা segment-এর ভেতরে থাকে (প্রতি level-এ একটা)। দুটো operation-ই হয়ে যায় O(log n)। ## 3. Array `[2, 5, 1, 4, 9, 3]`-এর উপরের tree-টা প্রতিটা node-এ লেখা `[range] = stored sum`: ```text [0..5] = 24 / \ [0..2] = 8 [3..5] = 16 / \ / \ [0..1] = 7 [2..2] = 1 [3..4] = 13 [5..5] = 3 / \ / \ [0..0]=2 [1..1]=5 [3..3]=4 [4..4]=9 array: index 0 1 2 3 4 5 value 2 5 1 4 9 3 ``` প্রতিটা internal node-এর পড়ার নিয়ম: **আমার value = বাঁ child-এর value + ডান child-এর value**। Root পুরো array-র answer ধরে রাখে। Tree-টা আমরা একটা flat list-এ রাখি: node `i`-র children হলো `2i+1` আর `2i+2` (0-indexed heap layout)। Size `4 * n` সবসময়ই যথেষ্ট। ## 4. Build — O(n) Recursive divide and conquer: `[lo..hi]` cover করা একটা node বানাতে হলে দুই অর্ধেক বানাও, তারপর combine করো। ```python def build(node, lo, hi): if lo == hi: # leaf: one element tree[node] = a[lo] return mid = (lo + hi) // 2 build(2 * node + 1, lo, mid) # left half build(2 * node + 2, mid + 1, hi) # right half tree[node] = tree[2 * node + 1] + tree[2 * node + 2] ``` `[2, 5, 1, 4, 9, 3]`-এর উপর frame-by-frame (আগে leaf-গুলো ভরে, তারপর recursion-এর ফেরার পথে parent-রা combine হয়): ```text frame 1: leaves set [0..0]=2 [1..1]=5 [2..2]=1 [3..3]=4 [4..4]=9 [5..5]=3 frame 2: level above combines [0..1] = 2 + 5 = 7 [3..4] = 4 + 9 = 13 frame 3: next level combines [0..2] = 7 + 1 = 8 [3..5] = 13 + 3 = 16 frame 4: root combines [0..5] = 8 + 16 = 24 done ``` প্রতিটা node ঠিক একবার computed হয় → build **O(n)**। ## 5. Query — O(log n) `sum of a[l..r]`-এর উত্তর দিতে প্রতিটা node-এ একটা three-way decision নিয়ে নিচে নামো: - node-এর range `[l..r]`-এর **পুরোপুরি ভেতরে** → তার জমা রাখা value নাও, থামো (সবুজ)। - node-এর range `[l..r]`-এর **পুরোপুরি বাইরে** → 0 contribute করো, থামো (লাল)। - node-এর range **আংশিক overlap করে** → দুই child-এই recurse করো (হলুদ)। ```python def query(node, lo, hi, l, r): if r < lo or hi < l: # fully outside return 0 if l <= lo and hi <= r: # fully inside return tree[node] mid = (lo + hi) // 2 # partial: split return (query(2*node+1, lo, mid, l, r) + query(2*node+2, mid+1, hi, l, r)) ``` `query(l=1, r=4)`-এর frame-গুলো — আসল answer হলো `5 + 1 + 4 + 9 = 19`: ```text frame 1: visit [0..5] partial overlap with [1..4] -> split frame 2: visit [0..2] partial -> split frame 3: visit [0..1] partial -> split frame 4: visit [0..0] OUTSIDE [1..4] -> return 0 frame 5: visit [1..1] INSIDE, take 5 -> return 5 frame 6: visit [2..2] INSIDE, take 1 -> return 1 frame 7: visit [3..5] partial -> split frame 8: visit [3..4] INSIDE, take 13 -> return 13 frame 9: visit [5..5] OUTSIDE -> return 0 answer = 0 + 5 + 1 + 13 + 0 = 19 (4 useful pieces, ~log n nodes touched) ``` Query-টা কিন্তু array কখনো scan করেনি। সে **ready segment** `[1..1]`, `[2..2]`, `[3..4]` জোড়া লাগিয়েছে মাত্র। ## 6. Point update — O(log n) `a[i] = v` set করতে: root থেকে leaf `i`-র দিকে হাঁটো, আর ফেরার পথে প্রতিটা parent-কে আবার combine করো। শুধু একটাই root-to-leaf path বদলায়। ```python def update(node, lo, hi, i, v): if lo == hi: # found the leaf tree[node] = v return mid = (lo + hi) // 2 if i <= mid: update(2*node+1, lo, mid, i, v) else: update(2*node+2, mid+1, hi, i, v) tree[node] = tree[2*node+1] + tree[2*node+2] # repair on the way up ``` `update(i=2, v=6)`-এর frame-গুলো (1-টাকে 6 বানাচ্ছি): ```text frame 1: at [0..5] i=2 <= mid=2 -> go left frame 2: at [0..2] i=2 > mid=1 -> go right frame 3: at [2..2] leaf! set value: [2..2] = 6 frame 4: back at [0..2] repair: 7 + 6 = 13 frame 5: back at [0..5] repair: 13 + 16 = 29 range before after [0..5] 24 29 changed [0..2] 8 13 changed [3..5] 16 16 [0..1] 7 7 [2..2] 1 6 changed [3..4] 13 13 [5..5] 3 3 [0..0] 2 2 [1..1] 5 5 [3..3] 4 4 [4..4] 9 9 exactly 3 nodes changed — the path from leaf to root. ``` এবার `query(1, 4)` সাথে সাথে return করে `5 + 6 + 13 = 24`। কোনো rebuild নেই, কোনো stale data নেই। ## 7. Complexity summary | Operation | Cost | কেন | | --- | --- | --- | | Build | O(n) | ~2n-টা node-এর প্রতিটা একবার computed হয় | | Range query | O(log n) | প্রতি level-এ ≤ ~2-টা node টেকে, level ~log n-টা | | Point update | O(log n) | ঠিক একটা root-to-leaf path repair হয় | | Memory | O(n) | size 4n-এর flat array safe | ## 8. কোনটা generalize হয়: যেকোনো associative combine উপরের কোনো কিছুই "sum"-এর উপর নির্ভর করেনি, শুধু combine step ছাড়া। সেটা বদলে ফেলো: | যা query করতে চাও | Combine | Identity ("outside" হলে return value) | | --- | --- | --- | | Range sum | `a + b` | `0` | | Range minimum | `min(a, b)` | `+infinity` | | Range maximum | `max(a, b)` | `-infinity` | | Range gcd | `gcd(a, b)` | `0` | একটাই requirement: operation-টা **associative** হতে হবে — `(a ∘ b) ∘ c == a ∘ (b ∘ c)` — কারণ tree element-গুলোকে fixed chunk-এ group করে, আর answer-টা grouping-এর উপর নির্ভর করলে চলবে না। Average সরাসরি জমানো যায় না (এটা associative নয়), কিন্তু `(sum, count)` pair জমানো যায় — richer data জমাও, শেষে average বের করো। এই trick-টা — *যা merge হয় তা জমাও, যা চাও তা derive করো* — অনেক segment-tree variant-এর দরজা খুলে দেয়। ## 9. Teaser: lazy propagation (range updates) উপরের সবকিছু **একটা** করে element update করে। যদি query বলে "`[l..r]`-এর প্রতিটা element-এ 10 যোগ করো"? প্রতিটা leaf update করলে O(n log n) — খুব slow। Idea-টা, এক বাক্যে: একটা update যখন কোনো node-এর segment-কে পুরোপুরি cover করে, তখন নিচে না নেমে **node-টার গায়ে একটা sticky note লিখে দাও** ("আমার নিচের সবাই +10 পাওনা") আর থেমে যাও; note-টা নিচে ঠেলে দাও শুধু তখনই, যখন ভবিষ্যতের কোনো operation-এর সত্যিই ওই subtree-তে ঢোকা দরকার। Update আবার O(log n) হয়ে যায়। এটাই **lazy propagation**। আমরা ইচ্ছে করেই এখানে teaser-এ থামছি — আগে plain build/query/update-এ master হও। পুরো treatment-এর জন্য দেখো [cp-algorithms on segment trees](https://cp-algorithms.com/data_structures/segment_tree.html)। ## এরপর কোথায় যাবে - উপরের সবকিছুর ছবি: [visual-explanation.md](visual-explanation.md)। - Sum-এর জন্য 10-লাইনের খুড়তুতো ভাই: [fenwick-tree.md](fenwick-tree.md)। - Assert-সহ runnable code: [implementation.py](implementation.py)।