Visual Explanation — Segment Tree and Fenwick Tree¶
এই folder-এর সবকিছু, ছবিতে আঁকা। এটা
segment-tree.mdআরfenwick-tree.md-এর পাশাপাশি রেখে পড়ো।
1. Tree-টা array-র উপরে বাস করে¶
Array থাকে মাটিতে। Tree তার উপরে ভাসে। Array [2, 5, 1, 4, 9, 3]-এর জন্য প্রতিটা node-এ লেখা [range] = stored sum:
+-------------+
| [0..5] = 24 | level 0 (root: whole array)
+-------------+
/ \
+------------+ +-------------+
| [0..2] = 8 | | [3..5] = 16 | level 1 (halves)
+------------+ +-------------+
/ \ / \
+-----------+ +----------+ +------------+ +----------+
| [0..1]=7 | | [2..2]=1 | | [3..4]=13 | | [5..5]=3 | level 2
+-----------+ +----------+ +------------+ +----------+
/ \ / \
+--------+ +--------+ +--------+ +--------+
|[0..0]=2| |[1..1]=5| |[3..3]=4| |[4..4]=9| level 3 (leaves)
+--------+ +--------+ +--------+ +--------+
| | | | | |
array: 2 5 1 4 9 3
index: 0 1 2 3 4 5
পড়ার মূল নিয়ম: প্রতিটা parent = বাঁ child + ডান child। Leaf-গুলোই আসলে array। মোট node মোটামুটি 2n-টা।
2. Query decomposition, frame by frame: query(1, 4)¶
আমরা চাই sum of a[1..4] = 5 + 1 + 4 + 9 = 19। Legend: ? = partial overlap (ভাঙতে হবে), TAKE = পুরোপুরি ভেতরে (জমা রাখা value নাও), skip = পুরোপুরি বাইরে।
frame 1 — start at the root
[0..5] ? covers 0..5, query is 1..4 -> partial, split
/ \
frame 2 — left subtree
[0..2] ? partial (0 is outside) -> split
/ \
[0..1] ? [2..2] TAKE 1 [2..2] sits inside [1..4]
frame 3 — split [0..1]
[0..0] skip [1..1] TAKE 5 0 is outside; 1 is inside
frame 4 — right subtree
[3..5] ? partial (5 is outside) -> split
/ \
[3..4] TAKE 13 [5..5] skip [3..4] fully inside; 5 outside
frame 5 — glue the taken pieces
answer = 5 + 1 + 13 = 19
নেওয়া segment-গুলো query-টাকে ঠিকঠাক tile করে:
~12-টা node-এর মধ্যে walk-টা 9-টায় গেছে আর ব্যবহার করেছে 3-টা। n = 1,000,000 হলে এই একই walk ~40-টা node ছোঁয় — O(log n)-এর promise-টা চোখের সামনে।
3. Point update, frame by frame: update(2, 6)¶
a[2]-কে 1 থেকে 6 বানাও। শুধু root-to-leaf path-টাই বদলায় (* দিয়ে marked):
frame 1 — descend to the leaf
[0..5]* -> [0..2]* -> [2..2]* (i=2: left, then right)
frame 2 — rewrite the leaf
[2..2] : 1 -> 6
frame 3 — repair parents on the way back up
[0..2] : 8 -> 7 + 6 = 13
[0..5] : 24 -> 13 + 16 = 29
after:
[0..5] = 29 *
/ \
[0..2] = 13 * [3..5] = 16
/ \ / \
[0..1]=7 [2..2]=6 * [3..4]=13 [5..5]=3
... ...
3 starred nodes changed. Everything else is untouched and still valid.
4. Fenwick skyline (n = 16)¶
প্রতিটা Fenwick index i দায়িত্ব নেয় lowbit(i)-টা element-এর একটা block-এর, যেটা i-তে শেষ হয়। Skyline হিসেবে আঁকলে (bar-এর width = covered block):
height = block size
16 | ┌──────────── 16 ───────────┐
8 | ┌───────── 8 ─────────┐
4 | ┌─── 4 ───┐ ┌── 12 ──┐
2 | ┌ 2 ┐ ┌ 6 ┐ ┌ 10 ┐ ┌ 14 ┐
1 | |1| |3| |5| |7| |9| |11| |13| |15|
─────────────────────────────────────────────────────────
elem: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Odd index-গুলো একটা মাত্র element cover করে। Power of two-গুলো পুরো prefix cover করে। বাকি সবাই মাঝারি size-এর block। যেকোনো prefix হলো কয়েকটা non-overlapping bar-এর stack।
5. Fenwick query jumps: prefix_sum(13)¶
নিয়ম: tree[i] নাও, তারপর i -= lowbit(i)। Binary digit-গুলো কীভাবে এক এক করে নিভে যায়, দেখো:
i = 13 = 1101₂ take tree[13] (block 13..13)
strip 0001 -> 12
i = 12 = 1100₂ take tree[12] (block 9..12)
strip 0100 -> 8
i = 8 = 1000₂ take tree[8] (block 1..8)
strip 1000 -> 0
i = 0 stop
picture of the tiling:
elements 1..13: [■■■■■■■■][■■■■][■]
tree[8] tree[12] tree[13]
1..8 9..12 13
3 hops = 3 set bits in 13. The binary form of i IS the tiling plan.
6. Fenwick update jumps: add(5, +10), n = 16-এ¶
নিয়ম: tree[i] bump করো, তারপর i += lowbit(i)। Walk-টা সেই প্রতিটা block-এ যায়, যার ভেতরে element 5 আছে:
i = 5 = 0101₂ tree[5] += 10 (block 5..5)
add 0001 -> 6
i = 6 = 0110₂ tree[6] += 10 (block 5..6)
add 0010 -> 8
i = 8 = 1000₂ tree[8] += 10 (block 1..8)
add 1000 -> 16
i = 16 = 10000₂ tree[16] += 10 (block 1..16)
add 10000 -> 32 > 16, stop
which bars in the skyline contain element 5?
16 | ┌──────────────── contains 5 ────────────────┐ tree[16] ✓
8 | ┌──── contains 5 ────┐ tree[8] ✓
2 | ┌ 5..6 ┐ tree[6] ✓
1 | |5| tree[5] ✓
────────────────────────────────────────────────
^ element 5
Update-গুলো skyline বেয়ে উপরে ওঠে (বড় block-এর দিকে); query-গুলো নিচে আর বাঁয়ে নামে (index 0-র দিকে)। দুটো walk একে অপরের mirror image, আর দুজনে মিলেই প্রতিটা prefix sum-কে সৎ রাখে।
7. প্রতিটা structure মনে রাখার একটা করে ছবি¶
SEGMENT TREE FENWICK TREE
"a tree of halves over the array" "a skyline of binary blocks"
[whole] tall bars at powers of two,
/ \ single-cell bars at odd indices;
[left half] [right half] navigate by adding/stripping
... ... ... ... the lowest set bit
any range = O(log n) ready pieces any prefix = one bar per set bit
Segment tree-র interactive version দেখতে চাইলে VisuAlgo ঘুরে এসো।