Skip to content

Problem Tracker — Segment Tree and Fenwick Tree

এটা এই 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।
  • 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-টা:

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 Prefix sums (tree লাগবেই না!) Math level 5 prefix sums 001-static-range-sum-queries.md planned
2 Range Sum Query — Immutable — একই idea, class-based API Easy LeetCode 303 Prefix sums baseline Math level 5 prefix sums 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 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 planned
5 Range Sum Query — Mutable — point update-সহ sums Medium LeetCode 307 Segment tree / Fenwick core Arrays, recursion 005-range-sum-query-mutable.md planned
6 Dynamic Range Sum Queries — #5-এর contest version Medium CSES 1648 Segment tree / Fenwick core Arrays, recursion 006-dynamic-range-sum-queries.md planned
7 Dynamic Range Minimum Queries — sum-এর বদলে min, update-সহ Medium CSES Problem Set — "Dynamic Range Minimum Queries" Min segment tree (Fenwick এখানে চলবে না) Segment tree generalization 007-dynamic-range-min-queries.md planned
8 Range Xor Queries — একটা static range-এর xor Medium CSES Problem Set — "Range Xor Queries" Prefix xor / invertible ops Math level 4 xor, prefix idea 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 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 planned
11 Forest Queries — 2D static range sums (খেয়াল করো: static হলে tree লাগে না) Medium CSES Problem Set — "Forest Queries" 2D prefix sums Math level 5, grids 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 planned
13 Count of Smaller Numbers After Self — প্রতিটা element-এর ডানে কতগুলো ছোট element বসে আছে Hard LeetCode 315 BIT + coordinate compression BIT over values, sorting 013-count-of-smaller-after-self.md planned
14 Reverse Pairs — i < j আর a[i] > 2·a[j] এমন (i, j) pair গোনো Hard LeetCode 493 BIT / merge-sort counting #10, #13 014-reverse-pairs.md planned
15 Hotel Queries — প্রতিটা group-এর জন্য, যথেষ্ট capacity-ওয়ালা প্রথম hotel খোঁজো Hard CSES Problem Set — "Hotel Queries" Walk down a max segment tree Max segment tree, binary descent 015-hotel-queries.md planned
16 Salary Queries — salary বদলাতে বদলাতে একটা salary range-এর employee গোনো Hard CSES Problem Set — "Salary Queries" BIT over compressed values Coordinate compression, BIT 016-salary-queries.md planned
17 My Calendar III — event আসতে আসতে maximum booking overlap track করো Hard LeetCode 732 Sweep line / lazy tree teaser Intervals, segment-on-values 017-my-calendar-iii.md planned
18 Codeforces থেকে rating-1500+ একটা unsolved data-structures problem বাছো; editorial খোলার আগে segment-tree signal-টা নিজে identify করো Hard Codeforces problemset Pattern recognition in the wild পুরো folder 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 section 4–6, তারপর frame-গুলো নিজে আবার আঁকো
i & (-i) jump-গুলো click করছে না ../visual-explanation.md section 5–6; prefix_sum(11) হাতে trace করো
[l, r] আর [l, r)-এর মধ্যে off-by-one-এর হযবরল ../implementation.py-র inclusive convention-টা নাও, আর প্রতিটা problem-কে boundary-তে ওই convention-এ convert করো
Counting problem-গুলোতে (#10, #13, #14, #16) wrong answer ../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-টা কেন বিকল্পগুলোর চেয়ে ভালো।