Segment Tree — শুধু Element নয়, Segment-এর Answer জমাও¶
একটা মাত্র 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/ থেকে। জমে থাকা (frozen) array-র জন্য এরা perfect:
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 এখন ভুল:
একটা 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-টা নাও আর অর্ধেক করতে থাকো:
বারবার অর্ধেক করে যত 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:
[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 করো।
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 হয়):
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 করো (হলুদ)।
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:
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 বদলায়।
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 বানাচ্ছি):
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
before: after:
[0..5]=24 [0..5]=29 <- changed
[0..2]=8 [3..5]=16 [0..2]=13 [3..5]=16
... [2..2]=1 ... ... [2..2]=6 ...
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।
এরপর কোথায় যাবে¶
- উপরের সবকিছুর ছবি:
visual-explanation.md। - Sum-এর জন্য 10-লাইনের খুড়তুতো ভাই:
fenwick-tree.md। - Assert-সহ runnable code:
implementation.py।