11 — Segment Tree and Fenwick Tree¶
Array-এর উপরে বসানো একটা tree, যেখানে প্রতিটা node array-র একটা পুরো segment-এর answer মনে রাখে — ফলে যেকোনো range-এর প্রশ্নের উত্তর হয় কয়েকটা ready-made টুকরো জোড়া লাগিয়ে।
এই structure-টা কী¶
Segment tree হলো একটা binary tree, যেখানে:
- leaf-গুলো হলো array-র এক-একটা আলাদা element, আর
- প্রতিটা internal node তার subtree যে contiguous range-টা cover করে, সেই range-এর জন্য একটা আগে থেকে হিসেব করা answer (sum, min, max, gcd, ...) জমা রাখে।
Fenwick tree (যাকে Binary Indexed Tree বা BIT-ও বলা হয়) হলো এর compressed খুড়তুতো ভাই: একটা flat array, যেখানে প্রতিটা index চালাকি করে বেছে নেওয়া একটা block-এর elements-এর "দায়িত্বে" থাকে। এর ফলে prefix sums বের করা আর point update করা — দুটোই O(log n)-এ হয়ে যায়, মোটে দশ লাইনের মতো code-এ।
এই structure-টা সরাসরি তোমার আগে থেকে জানা জিনিসগুলো থেকেই এসেছে:
- arrays (data-টা একটা array-তেই থাকে),
- recursion আর divide and conquer (
../06-recursion-and-backtracking/) — একটা range-কে অর্ধেক করো, প্রতিটা অর্ধেক solve করো, তারপর combine করো, - prefix sums দিয়ে range queries (
../01-math-based-programming-fundamentals/05-prefix-difference-contribution/)।
নতুন thinking tweak একটাই: শুধু আলাদা আলাদা element-এর answer জমানো বন্ধ করো। Segment-এর answer-ও জমাও। তাহলে যে range-ই জিজ্ঞেস করা হোক না কেন, সেটা O(log n)-টা segment-এর union — যাদের answer আগে থেকেই তৈরি হয়ে বসে আছে।
এটা কেন আছে (কোন ব্যথাটা দূর করে)¶
Prefix sums "একটা range-এর sum কত" — এর উত্তর O(1)-এ দেয়, কিন্তু শুধু তখনই, যখন array কখনো বদলায় না। একটা মাত্র update এলেই পুরো prefix array আবার বানাতে হয় — O(n)। q-টা update আর q-টা query মিশে থাকলে খরচ দাঁড়ায় O(n·q): n = q = 100,000 হলে একেবারে অসম্ভব।
Segment tree আর Fenwick tree-র কাজ হলো update + query একসাথে — এই ব্যথাটা সারানো:
| Approach | Range query | Point update |
|---|---|---|
| Plain array | O(n) | O(1) |
| Prefix sums | O(1) | O(n) |
| Segment tree / Fenwick | O(log n) | O(log n) |
কোনো operation-ই একদম সবচেয়ে দ্রুত নয়, কিন্তু দুটোই দ্রুত। এই balance-টাই পুরো ব্যাপার।
কোথায় ব্যবহার হয়¶
- Competitive programming: update-সহ range sum/min/max/gcd একদম রোজকার (bread-and-butter) task।
- Order statistics: "আমার পরে কয়টা ছোট element আসে?" (inversion গোনা)।
- Database আর analytics engine: pre-aggregated range answer।
- Game-এর leaderboard: live বদলাতে থাকা score-এর মধ্যে একজন player-এর rank।
- Computational geometry: sweep-line algorithm যেগুলো event গোনে বা aggregate করে।
- Range Sum Query — Mutable-এর মতো interview problem।
Prerequisites¶
- Arrays আর indexing (
../02-arrays-and-strings/)। - Recursion: এমন function লেখা যেটা নিজেকেই অর্ধেক-অর্ধেক range-এ call করে (
../06-recursion-and-backtracking/)। - Trees, অন্তত "একটা node-এর children থাকে" — এই intuition level-এ (
../07-trees/)। - Prefix sums (
../01-math-based-programming-fundamentals/05-prefix-difference-contribution/)। - Fenwick-এর জন্য: integer-এর binary representation আর last set bit (math fundamentals, bit manipulation level)।
শেখার আগে কী revise করবে¶
- Prefix sums কীভাবে range sum-এর উত্তর দেয়:
prefix[r+1] - prefix[l]। - এমন একটা recursive function যেটা
(lo, hi)-কে(lo, mid)আর(mid+1, hi)-তে ভাঙে — merge sort এর জন্য perfect refresher। mid = (lo + hi) // 2আর এটা কেন কখনো bound-এর বাইরে যায় না।- ছোট সংখ্যার binary: 6 =
110, 12 =1100, আর "last set bit" মানে কী।
Learning goals (checklist)¶
- [ ] এক বাক্যে বোঝাতে পারো — update এলে prefix sums কেন ভেঙে পড়ে।
- [ ]
[2, 5, 1, 4, 9, 3]-এর segment tree কাগজে আঁকতে পারো, range-গুলো label করে। - [ ] একটা range-sum query trace করে দেখাতে পারো — সেটা শুধু O(log n)-টা node ছোঁয়।
- [ ] একটা point update trace করে দেখাতে পারো — সেটা ঠিক একটাই root-to-leaf path ঠিক করে।
- [ ] Merge function-টা কেন associative হতেই হবে, বোঝাতে পারো (sum, min, max, gcd সবগুলোই qualify করে)।
- [ ] x = 5, 6, 12-এর জন্য
lowbit(x) = x & (-x)হাতে হাতে বের করতে পারো। - [ ] Index 8 পর্যন্ত প্রতিটা Fenwick index কোন range-এর দায়িত্বে, এঁকে দেখাতে পারো।
- [ ] Fenwick tree-তে
prefix_sum(13)আরadd(5, delta)-র index jump-গুলো trace করতে পারো। - [ ] কখন segment tree-র বদলে Fenwick নেবে, আর কখন Fenwick দিয়ে হবেই না — বলতে পারো।
- [ ] দুটো structure-ই 15 মিনিটের কমে মুখস্থ থেকে implement করতে পারো।
Problem categories¶
| Category | Typical question shape |
|---|---|
| Range sum + point update | "[l, r]-এর মধ্যে value-গুলোর sum, value-গুলো বদলাতেই থাকে" |
| Range min / max | "একটা window-র সবচেয়ে সস্তা জিনিস, price update-সহ" |
| Counting / order statistics | "x-এর চেয়ে ছোট কয়টা element এখন পর্যন্ত এসেছে?" |
| Inversion counting | "কয়টা pair উল্টো order-এ আছে?" |
| Coordinate compression + BIT | "Value 10^9 পর্যন্ত, কিন্তু মাত্র n-টাই গুরুত্বপূর্ণ" |
| Sweep line + tree | "Event-গুলো বাঁ থেকে ডানে process করো, যা দেখা হয়েছে তা aggregate করো" |
Practice list¶
নিচের problem statement-গুলো আমাদের নিজেদের ভাষায় লেখা; official statement-এর জন্য link-গুলো follow করো।
Easy¶
| Problem | Source | Pattern |
|---|---|---|
| Static Range Sum Queries — অনেকগুলো range sum, কোনো update নেই (warm-up: এখানে prefix sums-ই tree-কে হারায়) | CSES 1646 | Prefix sums baseline |
| Range Sum Query — Immutable — একই idea, LeetCode flavor | LeetCode 303 | Prefix sums baseline |
| 6-element array-র জন্য কাগজে একটা max segment tree বানাও আর হাতে হাতে 3-টা query-র উত্তর দাও | (self-exercise, কোনো judge নেই) | Build + query tracing |
| ছোট একটা array-র inversion সংখ্যা brute force দিয়ে বের করো, তারপর BIT দিয়ে verify করো | (self-exercise, কোনো judge নেই) | Counting with BIT |
Medium¶
| Problem | Source | Pattern |
|---|---|---|
| Range Sum Query — Mutable — point update-সহ sum | LeetCode 307 | Segment tree / Fenwick core |
| Dynamic Range Sum Queries — একই task-এর CSES version | CSES 1648 | Segment tree / Fenwick core |
| Dynamic Range Minimum Queries | CSES Problem Set — "Dynamic Range Minimum Queries" | Min segment tree |
| Range Xor Queries | CSES Problem Set — "Range Xor Queries" | Prefix xor / segment tree |
| Merge-sort করতে করতে inversion গোনো, তারপর Fenwick tree দিয়ে আবার করো | (self-exercise; classic, judge ছাড়া) | Inversions via BIT |
| Forest Queries — 2D prefix sums (contrast: static 2D-তে কোনো tree লাগে না) | CSES Problem Set — "Forest Queries" | 2D prefix sums |
Hard¶
| Problem | Source | Pattern |
|---|---|---|
| Count of Smaller Numbers After Self — প্রতিটা element-এর জন্য তার ডানদিকের ছোট element গোনো | LeetCode 315 | BIT + coordinate compression |
| Reverse Pairs — এমন pair গোনো যেখানে বাঁদিকের value > 2 × ডানদিকের value | LeetCode 493 | BIT / merge-sort counting |
| Hotel Queries — যথেষ্ট খালি room-ওয়ালা প্রথম hotel-টা খোঁজো (max tree বেয়ে নিচে নামো) | CSES Problem Set — "Hotel Queries" | Segment tree descent |
| Salary Queries — value update-সহ range count | CSES Problem Set — "Salary Queries" | BIT over values |
| My Calendar III — সর্বোচ্চ কয়টা booking overlap করে | LeetCode 732 | Sweep / lazy segment tree teaser |
| Codeforces problem set থেকে rating-1500+ যেকোনো data-structures problem তুলে নাও, আর editorial পড়ার আগে নিজে segment-tree signal-টা চিনে ফেলো | Codeforces problemset | Pattern recognition |
Visualization ideas¶
- Array-টাকে 6-টা box হিসেবে আঁকো, তারপর tree-টা তার উপরে আঁকো, প্রতিটা node-এ তার
[l..r]range আর জমা রাখা sum label করে। - একটা query যে node-গুলো ছোঁয় সেগুলো রং করো: সবুজ = fully inside (নাও আর থামো), লাল = fully outside (skip করো), হলুদ = partial (recurse করো)।
- Fenwick-এর জন্য index 1..16-কে column হিসেবে আঁকো, যাদের height হলো ওই index যে block cover করে তার size — powers of two-র একটা skyline।
prefix_sum(13)animate করো: 13 → 12 → 8 → 0, প্রতি hop-এ একটা করে set bit ঝরে পড়ছে।- VisuAlgo-তে একটা interactive segment tree আছে: visualgo.net।
Common mistakes (সাধারণ ভুল)¶
- প্রতিটা update-এর পর prefix sums আবার বানানো, আর তারপর ভাবা solution-টা time out করছে কেন।
- Inclusive
[l, r]আর half-open[l, r)query convention-এর মধ্যে off-by-one — একটা বেছে নাও আর কখনো মেশাবে না। - ভুলে যাওয়া যে Fenwick tree ভেতরে ভেতরে 1-indexed; index 0 চুপচাপ
x & (-x)loop ভেঙে দেয়। - Code-এ
add(i, delta)semantics আছে অথচupdate(i, value)semantics ধরে চালানো, বা উল্টোটা। - Prefix sum-এর জন্য বানানো Fenwick tree-তে min/max query চালানোর চেষ্টা — plain Fenwick শুধু invertible operation (যেমন sum) সামলায় arbitrary range-এর জন্য; min/max-এর জন্য segment tree চাই।
- Tree array-টা ছোট size-এ বানানো; recursive segment tree-র জন্য
4 * nহলো safe size। - Non-associative function দিয়ে merge করা — tree চুপচাপ আবর্জনা return করবে।
Interview problems-এর সাথে connection¶
Range Sum Query — Mutable হলো interview-র canonical gateway। Count of Smaller Numbers After Self একটা frequently seen interview pattern যেটা দেখতে sorting-এর মতো, কিন্তু আসলে order statistics — একটা BIT আর coordinate compression-ই এটাকে ভেঙে দেয়। Interviewer-রা এগুলো ভালোবাসে, কারণ এগুলো test করে — update এলে তুমি prefix sums-এর ওপারে পৌঁছাতে পারো কি না। এগুলো অন্য topic-এর সাথে কীভাবে মেশে, দেখো ../13-interview-master-problems/-এ।
Competitive programming-এর সাথে connection¶
Contest-এ segment tree "advanced" কিছু নয় — ধরেই নেওয়া হয় তুমি জানো। CSES-এ পুরো একটা Range Queries chapter আছে; Codeforces Div. 2-র C–E problem-গুলোতে গল্পের আড়ালে নিয়মিত একটা segment tree বা BIT লুকিয়ে থাকে। Lazy propagation (range updates), persistence, আর segment tree beats — সবই এখানে শেখানো structure-টার উপরেই দাঁড়িয়ে। লেখার speed যখন matter করে, Fenwick tree জেতে: time pressure-এ মোটে 10 লাইন।
Recommended learning order¶
README.md— এই file-টা, পুরো map-এর জন্য।segment-tree.md— prefix sums কেন fail করে, তারপর frame-সহ build / query / update।visual-explanation.md— একই machinery-র ছবি; step 2-এর পাশাপাশি পড়ো।fenwick-tree.md— compressed বিকল্পটা, আর কোনটা কখন ব্যবহার করবে।implementation.py— চালাও, ভাঙো, মুখস্থ থেকে আবার implement করো।problems/README.md— tracker ধরে কাজ করো, easy থেকে hard।
Source map¶
এই folder-এর সব source, link, আর copying status-এর তালিকা আছে source-map.md-এ।