# 11 — Segment Tree and Fenwick Tree

> **এখান থেকে শুরু করুন:** [সহজ ব্যাখ্যা, শেখার ক্রম ও বাস্তব ব্যবহার](learning-guide.md) → [প্রশ্ন, official link ও স্থানীয় সমাধান](problems/README.md)। [উৎসের তালিকা](source-map.md)-এ reference পাবেন।

> 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/](../06-recursion-and-backtracking/README.md)) — একটা range-কে অর্ধেক করো, প্রতিটা অর্ধেক solve করো, তারপর combine করো,
- **prefix sums দিয়ে range queries** ([../01-math-based-programming-fundamentals/05-prefix-difference-contribution/](../01-math-based-programming-fundamentals/05-prefix-difference-contribution/README.md))।

নতুন **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/](../02-arrays-and-strings/README.md))।
- Recursion: এমন function লেখা যেটা নিজেকেই অর্ধেক-অর্ধেক range-এ call করে ([../06-recursion-and-backtracking/](../06-recursion-and-backtracking/README.md))।
- Trees, অন্তত "একটা node-এর children থাকে" — এই intuition level-এ ([../07-trees/](../07-trees/README.md))।
- Prefix sums ([../01-math-based-programming-fundamentals/05-prefix-difference-contribution/](../01-math-based-programming-fundamentals/05-prefix-difference-contribution/README.md))।
- 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-কে হারায়) · [ব্যাখ্যা](problems/001-static-range-sum-queries.md) | [CSES 1646](https://cses.fi/problemset/task/1646) | Prefix sums baseline |
| Range Sum Query — Immutable — একই idea, LeetCode flavor · [ব্যাখ্যা](problems/002-range-sum-query-immutable.md) | [LeetCode 303](https://leetcode.com/problems/range-sum-query-immutable/) | 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 · [ব্যাখ্যা](problems/005-range-sum-query-mutable.md) | [LeetCode 307](https://leetcode.com/problems/range-sum-query-mutable/) | Segment tree / Fenwick core |
| Dynamic Range Sum Queries — একই task-এর CSES version · [ব্যাখ্যা](problems/006-dynamic-range-sum-queries.md) | [CSES 1648](https://cses.fi/problemset/task/1648) | Segment tree / Fenwick core |
| Dynamic Range Minimum Queries · [ব্যাখ্যা](problems/007-dynamic-range-min-queries.md) | [CSES 1649 · Dynamic Range Minimum Queries](https://cses.fi/problemset/task/1649) | Min segment tree |
| Range Xor Queries · [ব্যাখ্যা](problems/008-range-xor-queries.md) | [CSES 1650 · Range Xor Queries](https://cses.fi/problemset/task/1650) | 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 লাগে না) · [ব্যাখ্যা](problems/011-forest-queries.md) | [CSES 1652 · Forest Queries](https://cses.fi/problemset/task/1652) | 2D prefix sums |

### Hard

| Problem | Source | Pattern |
| --- | --- | --- |
| Count of Smaller Numbers After Self — প্রতিটা element-এর জন্য তার ডানদিকের ছোট element গোনো · [ব্যাখ্যা](problems/013-count-of-smaller-after-self.md) | [LeetCode 315](https://leetcode.com/problems/count-of-smaller-numbers-after-self/) | BIT + coordinate compression |
| Reverse Pairs — এমন pair গোনো যেখানে বাঁদিকের value > 2 × ডানদিকের value · [ব্যাখ্যা](problems/014-reverse-pairs.md) | [LeetCode 493](https://leetcode.com/problems/reverse-pairs/) | BIT / merge-sort counting |
| Hotel Queries — যথেষ্ট খালি room-ওয়ালা প্রথম hotel-টা খোঁজো (max tree বেয়ে নিচে নামো) · [ব্যাখ্যা](problems/015-hotel-queries.md) | [CSES 1143 · Hotel Queries](https://cses.fi/problemset/task/1143) | Segment tree descent |
| Salary Queries — value update-সহ range count · [ব্যাখ্যা](problems/016-salary-queries.md) | [CSES 1144 · Salary Queries](https://cses.fi/problemset/task/1144) | BIT over values |
| My Calendar III — সর্বোচ্চ কয়টা booking overlap করে · [ব্যাখ্যা](problems/017-my-calendar-iii.md) | [LeetCode 732](https://leetcode.com/problems/my-calendar-iii/) | Sweep / lazy segment tree teaser |
| Codeforces problem set থেকে rating-1500+ যেকোনো data-structures problem তুলে নাও, আর editorial পড়ার আগে নিজে segment-tree signal-টা চিনে ফেলো · [ব্যাখ্যা](problems/018-codeforces-wild-pick.md) | [Codeforces problemset](https://codeforces.com/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](https://visualgo.net/en)।

## 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/](../13-interview-master-problems/README.md)-এ।

## 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

1. [README.md](README.md) — এই file-টা, পুরো map-এর জন্য।
2. [segment-tree.md](segment-tree.md) — prefix sums কেন fail করে, তারপর frame-সহ build / query / update।
3. [visual-explanation.md](visual-explanation.md) — একই machinery-র ছবি; step 2-এর পাশাপাশি পড়ো।
4. [fenwick-tree.md](fenwick-tree.md) — compressed বিকল্পটা, আর কোনটা কখন ব্যবহার করবে।
5. [implementation.py](implementation.py) — চালাও, ভাঙো, মুখস্থ থেকে আবার implement করো।
6. [problems/README.md](problems/README.md) — tracker ধরে কাজ করো, easy থেকে hard।

## Source map

এই folder-এর সব source, link, আর copying status-এর তালিকা আছে [source-map.md](source-map.md)-এ।