# Problem Tracker — Segment Tree and Fenwick Tree

[অধ্যায়ে ফিরুন](../README.md) · [সহজ ব্যাখ্যা ও ব্যবহার](../learning-guide.md) · [উৎসের তালিকা](../source-map.md)

> **লিংক পড়ার নিয়ম:** Source খুললে প্ল্যাটফর্মের মূল প্রশ্ন, Note file খুললে এই সাইটের ব্যাখ্যা ও সমাধান পাবেন। নোটগুলো আগে থেকেই লেখা আছে। `planned` হলো আপনার ব্যক্তিগত অনুশীলনের অবস্থা, নোট অনুপস্থিত থাকার চিহ্ন নয়। প্ল্যাটফর্মের কিছু প্রশ্নে লগইন বা Premium লাগতে পারে; স্থানীয় নোট সরাসরি পড়া যাবে।

এটা এই topic-এর working ledger। উপর থেকে নিচে solve করো: list-টা "prefix sums-ই এখনো জেতে" warm-up দিয়ে শুরু করে, core update+query problem-গুলো পেরিয়ে, order statistics আর tree-walking trick-এ গিয়ে উঠেছে।

## How to use this tracker (এই tracker কীভাবে ব্যবহার করবে)

- প্রতিটা problem কিছু না পড়ে, cold অবস্থায় অন্তত 30 মিনিট চেষ্টা করো।
- Solve করার পর (বা সৎভাবে হাল ছাড়ার পর), এই folder-এই একটা note file লেখো — নাম হবে ঠিক **Note file** column-এ যা লেখা আছে, template: [../../templates/ds-problem-note-template.md](../../templates/ds-problem-note-template.md)।
- **Status** update করতে থাকো: `planned` → `attempted` → `solved` → `revisit`।
- এখানে সব problem statement নিজেদের ভাষায় paraphrase করা; official statement-টা link-এ গিয়ে অবশ্যই পড়ো।

## How to read a row (একটা row কীভাবে পড়বে)

- **Pattern** column-টা বলে problem-টা ঠিক কোন trick-টা train করে — solve করার পরেও যদি নিজে নামটা বলতে না পারো, problem-টা শেষ হয়নি।
- **Inherits from** দেখায় problem-টা কোন আগের skill-এর উপর দাঁড়িয়ে; সেখানে আটকালে আগে ওই folder-এ ফিরে যাও, তারপর এগোও।
- Self-exercise-গুলো (judge link নেই) ইচ্ছে করে রাখা: hand-tracing আর blank-file reimplementation এমন বোঝাপড়া তৈরি করে যা judge পরীক্ষা করতে পারে না।

## Before you start: the decision drill (শুরুর আগে)

নিচের প্রতিটা problem-এর জন্য, কোনো code লেখার আগে, এক লাইনে লেখো: *"Prefix sums, Fenwick, না segment tree — আর কেন?"* সৎ decision tree-টা:

```text
no updates?            -> prefix sums (do not build a tree for a frozen array)
updates + sums/counts? -> Fenwick (shortest correct code)
updates + min/max/gcd,
or range updates,
or tree-descent tricks? -> segment tree
```

Problem #1, #2, #8 আর #11 ঠিক এই কারণেই আছে — over-building ধরার জন্য। Static array-র উপর tree বানানোটা spirit-এ ভুল উত্তর, এমনকি pass করলেও।

## The list

| # | Problem | Difficulty | Source | Pattern | Inherits from | Note file | Status |
| --- | --- | --- | --- | --- | --- | --- | --- |
| 1 | Static Range Sum Queries — frozen array-র উপর অনেকগুলো range sum | Easy | [CSES 1646](https://cses.fi/problemset/task/1646) | Prefix sums (tree লাগবেই না!) | Math level 5 prefix sums | [001-static-range-sum-queries.md](001-static-range-sum-queries.md) | planned |
| 2 | Range Sum Query — Immutable — একই idea, class-based API | Easy | [LeetCode 303](https://leetcode.com/problems/range-sum-query-immutable/) | Prefix sums baseline | Math level 5 prefix sums | [002-range-sum-query-immutable.md](002-range-sum-query-immutable.md) | planned |
| 3 | [2,5,1,4,9,3]-এর জন্য sum segment tree হাতে বানাও; query(1,4), query(0,2), query(3,5)-এর উত্তর কাগজে বের করো | Easy | self-exercise | Build + query tracing | Recursion, divide and conquer | [003-hand-build-segment-tree.md](003-hand-build-segment-tree.md) | planned |
| 4 | n = 16-তে Fenwick prefix_sum(13) আর add(5, +10) hand-trace করো, প্রতিটা visited index লিখে | Easy | self-exercise | Lowbit navigation | Bit manipulation (math level 4) | [004-hand-trace-fenwick-jumps.md](004-hand-trace-fenwick-jumps.md) | planned |
| 5 | Range Sum Query — Mutable — point update-সহ sums | Medium | [LeetCode 307](https://leetcode.com/problems/range-sum-query-mutable/) | Segment tree / Fenwick core | Arrays, recursion | [005-range-sum-query-mutable.md](005-range-sum-query-mutable.md) | planned |
| 6 | Dynamic Range Sum Queries — #5-এর contest version | Medium | [CSES 1648](https://cses.fi/problemset/task/1648) | Segment tree / Fenwick core | Arrays, recursion | [006-dynamic-range-sum-queries.md](006-dynamic-range-sum-queries.md) | planned |
| 7 | Dynamic Range Minimum Queries — sum-এর বদলে min, update-সহ | Medium | [CSES 1649 · Dynamic Range Minimum Queries](https://cses.fi/problemset/task/1649) | Min segment tree (Fenwick এখানে চলবে না) | Segment tree generalization | [007-dynamic-range-min-queries.md](007-dynamic-range-min-queries.md) | planned |
| 8 | Range Xor Queries — একটা static range-এর xor | Medium | [CSES 1650 · Range Xor Queries](https://cses.fi/problemset/task/1650) | Prefix xor / invertible ops | Math level 4 xor, prefix idea | [008-range-xor-queries.md](008-range-xor-queries.md) | planned |
| 9 | Blank file থেকে দুটো structure-ই আবার লেখো, repo-র assert-গুলো তাদের উপর চালাও | Medium | self-exercise (use ../implementation.py tests) | From-memory implementation | পুরো folder | [009-blank-file-reimplementation.md](009-blank-file-reimplementation.md) | planned |
| 10 | একটা array-র inversion গোনো — প্রথমে merge sort দিয়ে, তারপর Fenwick tree দিয়ে, compare করো | Medium | self-exercise (classic) | Counting with BIT | Sorting, BIT over values | [010-count-inversions-two-ways.md](010-count-inversions-two-ways.md) | planned |
| 11 | Forest Queries — 2D static range sums (খেয়াল করো: static হলে tree লাগে না) | Medium | [CSES 1652 · Forest Queries](https://cses.fi/problemset/task/1652) | 2D prefix sums | Math level 5, grids | [011-forest-queries.md](011-forest-queries.md) | planned |
| 12 | Value-indexed tree দিয়ে Number of Longest Increasing Subsequence-ধাঁচের counting (folder 12 শেষ করার পরে) | Medium | self-exercise bridging to DP | BIT accelerates DP transitions | Folder 12 LIS + এই folder | [012-bit-accelerated-lis.md](012-bit-accelerated-lis.md) | planned |
| 13 | Count of Smaller Numbers After Self — প্রতিটা element-এর ডানে কতগুলো ছোট element বসে আছে | Hard | [LeetCode 315](https://leetcode.com/problems/count-of-smaller-numbers-after-self/) | BIT + coordinate compression | BIT over values, sorting | [013-count-of-smaller-after-self.md](013-count-of-smaller-after-self.md) | planned |
| 14 | Reverse Pairs — i < j আর a[i] > 2·a[j] এমন (i, j) pair গোনো | Hard | [LeetCode 493](https://leetcode.com/problems/reverse-pairs/) | BIT / merge-sort counting | #10, #13 | [014-reverse-pairs.md](014-reverse-pairs.md) | planned |
| 15 | Hotel Queries — প্রতিটা group-এর জন্য, যথেষ্ট capacity-ওয়ালা প্রথম hotel খোঁজো | Hard | [CSES 1143 · Hotel Queries](https://cses.fi/problemset/task/1143) | Walk down a max segment tree | Max segment tree, binary descent | [015-hotel-queries.md](015-hotel-queries.md) | planned |
| 16 | Salary Queries — salary বদলাতে বদলাতে একটা salary range-এর employee গোনো | Hard | [CSES 1144 · Salary Queries](https://cses.fi/problemset/task/1144) | BIT over compressed values | Coordinate compression, BIT | [016-salary-queries.md](016-salary-queries.md) | planned |
| 17 | My Calendar III — event আসতে আসতে maximum booking overlap track করো | Hard | [LeetCode 732](https://leetcode.com/problems/my-calendar-iii/) | Sweep line / lazy tree teaser | Intervals, segment-on-values | [017-my-calendar-iii.md](017-my-calendar-iii.md) | planned |
| 18 | Codeforces থেকে rating-1500+ একটা unsolved data-structures problem বাছো; editorial খোলার আগে segment-tree signal-টা নিজে identify করো | Hard | [Codeforces 339D · Xenia and Bit Operations](https://codeforces.com/problemset/problem/339/D) · [অন্য প্রশ্ন](https://codeforces.com/problemset/) | Pattern recognition in the wild | পুরো folder | [018-codeforces-wild-pick.md](018-codeforces-wild-pick.md) | planned |

## Milestones

- #6-এর পরে: যেকোনো "sum with updates" problem দেখা মাত্র solve করতে পারবে।
- #10-এর পরে: BIT-কে শুধু summer না, একটা *frequency counter* হিসেবেও বুঝবে।
- #14-এর পরে: coordinate compression + BIT একটা reflex হয়ে যাবে।
- #18-এর পরে: কেউ না বলে দিলেও structure-টা নিজেই চিনতে পারবে — আসল লক্ষ্য এটাই।

## When you get stuck (আটকে গেলে)

| Symptom | Where to go |
| --- | --- |
| Build/query-র recursion ঝাপসা লাগছে | [../segment-tree.md](../segment-tree.md) section 4–6, তারপর frame-গুলো নিজে আবার আঁকো |
| `i & (-i)` jump-গুলো click করছে না | [../visual-explanation.md](../visual-explanation.md) section 5–6; prefix_sum(11) হাতে trace করো |
| [l, r] আর [l, r)-এর মধ্যে off-by-one-এর হযবরল | [../implementation.py](../implementation.py)-র inclusive convention-টা নাও, আর প্রতিটা problem-কে boundary-তে ওই convention-এ convert করো |
| Counting problem-গুলোতে (#10, #13, #14, #16) wrong answer | [../fenwick-tree.md](../fenwick-tree.md) section 9-এর "BIT as a frequency table" আবার পড়ো — ওখানে index মানে একটা VALUE, position নয় |
| Tree থাকা সত্ত্বেও time limit exceeded | দেখো প্রতি query-তে rebuild করছ কি না, আর input parsing bottleneck হয়ে যাচ্ছে কি না |

এখানে কোনো problem `solved` mark করা মানে: judge pass করেছে এবং মুখস্থ থেকে বলতে পারো, ওই task-এ বেছে নেওয়া structure-টা কেন বিকল্পগুলোর চেয়ে ভালো।