# Fenwick Tree (Binary Indexed Tree) — Update সহ্য করা Prefix Sums [অধ্যায়ের সূচি](README.md) · [সহজ ব্যাখ্যা ও বাস্তব ব্যবহার](learning-guide.md) · [অনুশীলন ও সমাধান](problems/README.md) > Sum-এর জন্য segment tree-র মতোই superpower, code-এর দশ ভাগের এক ভাগে: একটা flat array, যেখানে প্রতিটা index চুপচাপ কিছু element-এর একটা block-এর দায়িত্ব নেয়, আর navigation-টা করে binary arithmetic। --- ## 1. এক লাইনের pitch Fenwick tree হলো **prefix sums যেগুলো update সহ্য করে**। `prefix_sum(i)` আর `add(i, delta)` — দুটোই O(log n)-এ চলে, আর পুরো structure-টা একটা array আর দুটো ছোট্ট loop। Segment tree যদি Swiss-army knife হয়, Fenwick tree হলো scalpel: কাজ কম পারে (মূলত prefix-ধাঁচের, invertible aggregation — যেমন sum আর count), কিন্তু লিখতে ছোট, memory-তে হালকা, আর practice-এ দ্রুত। ## 2. মূল idea: প্রতিটা index একটা block-এর দায়িত্বে Prefix-sum array-তে entry `i` জমা রাখে `i` পর্যন্ত *সবকিছুর* sum — সেজন্যই একটা update তার পরের সবকিছু ভেঙে দেয়। Fenwick-এর fix: entry `i` জমা রাখে শুধু `i`-তে শেষ হওয়া একটা **block**-এর element-গুলোর sum। Block-টার size ঠিক হয় `i`-র binary form দেখে: > **Index `i` দায়ী `i`-তে শেষ হওয়া শেষ `lowbit(i)`-টা element-এর জন্য**, যেখানে `lowbit(i)` হলো `i`-র lowest set bit-এর value। ```text lowbit(i) = i & (-i) i = 6 = 110₂ -> lowbit = 10₂ = 2 (responsible for elements 5..6) i = 12 = 1100₂ -> lowbit = 100₂ = 4 (responsible for elements 9..12) i = 8 = 1000₂ -> lowbit = 1000₂ = 8 (responsible for elements 1..8) i = 5 = 101₂ -> lowbit = 1₂ = 1 (responsible for element 5 only) ``` `i & (-i)` কেন last set bit বের করে? Two's complement-এ `-i` মানে `i`-র প্রতিটা bit flip করে 1 যোগ করা — ফলে ঠিক lowest set bit-টা (আর তার নিচের সবকিছু) `i`-র সাথে মেলে। এটা সেই একই bit trick যেটা তুমি math fundamentals-এর bit-manipulation level-এ (math level 4) দেখেছ — Fenwick tree-ই সেই জায়গা যেখানে trick-টা তার দাম আদায় করে। **Fenwick tree 1-indexed।** Index 0-র `lowbit(0) = 0`, আর সেটা চিরকাল loop করত; আমরা ওটা কখনো ব্যবহারই করি না। ## 3. Responsibility-র ছবি (n = 16) প্রতিটা bar দেখায় `tree[i]` মূল element-গুলোর কোন block cover করে: ```text elements: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 tree[16]: [================ 1..16 ================] tree[8]: [===== 1..8 =====] tree[12]: [== 9..12 ==] tree[4]: [ 1..4 ] tree[14]: [13..14] tree[6]: [5..6] tree[10]: [9..10] tree[2]: [1..2] tree[1]: [1] tree[3]: [3] tree[5]: [5] tree[7]: [7] tree[9]: [9] tree[11]: [11] tree[13]: [13] tree[15]: [15] ``` দুটো pattern খেয়াল করো: - Powers of two (`1, 2, 4, 8, 16`) এমন block cover করে যেগুলো element 1 থেকে শুরু — এরা হলো "checkpoint" prefix। - Odd index-গুলো ঠিক নিজেদেরই cover করে — এরা এই implicit tree-র leaf। - যেকোনো prefix `1..i`-কে hop করে করে tile করা যায়: `tree[i]` নাও, তারপর `i`-র block-এর ঠিক *আগের* prefix-এ লাফ দাও, আবার করো। ## 4. `prefix_sum(i)` — last set bit ঝেড়ে ফেলো, বাঁয়ে hop দাও Element `1..i`-র sum বের করতে: `tree[i]` নাও (এটা `i`-তে শেষ হওয়া block-টা cover করে), তারপর `i - lowbit(i)`-তে লাফ দাও — ওই block-এর ঠিক আগের index-টা — আর 0-তে না পৌঁছানো পর্যন্ত repeat করো। ```python def prefix_sum(i): # sum of elements 1..i s = 0 while i > 0: s += tree[i] i -= i & (-i) # strip the lowest set bit return s ``` `prefix_sum(13)`-এর walkthrough, frame-সহ: ```text 13 = 1101₂ frame 1: i = 13 (1101₂) take tree[13] (covers 13..13) strip lowbit 1: 13 - 1 = 12 frame 2: i = 12 (1100₂) take tree[12] (covers 9..12) strip lowbit 4: 12 - 4 = 8 frame 3: i = 8 (1000₂) take tree[8] (covers 1..8) strip lowbit 8: 8 - 8 = 0 frame 4: i = 0 stop blocks visited: [1..8] + [9..12] + [13..13] = exactly 1..13, no gaps, no overlap hops = number of set bits in 13 = 3 ≤ log₂(n) ``` `i`-র binary form-টাই *হলো* tiling plan: প্রতিটা set bit একটা করে block দেয়। ## 5. `add(i, delta)` — উল্টো হাঁটা, ডানদিকে hop Element `i`-তে `delta` যোগ করতে হলে, element `i`-কে *ধারণ করা* প্রতিটা block-কে জানাতে হবে। সেই block-গুলো পাওয়া যায় বারবার lowbit **যোগ** করে: ```python def add(i, delta): # element i += delta while i <= n: tree[i] += delta i += i & (-i) # jump to the next block that contains element i return ``` n = 16-তে `add(5, +10)`-এর walkthrough: ```text 5 = 101₂ frame 1: i = 5 (0101₂) tree[5] += 10 (block 5..5 contains 5) add lowbit 1: 5 + 1 = 6 frame 2: i = 6 (0110₂) tree[6] += 10 (block 5..6 contains 5) add lowbit 2: 6 + 2 = 8 frame 3: i = 8 (1000₂) tree[8] += 10 (block 1..8 contains 5) add lowbit 8: 8 + 8 = 16 frame 4: i = 16 (10000₂) tree[16] += 10 (block 1..16 contains 5) add lowbit 16: 16 + 16 = 32 > n -> stop 4 entries touched ≤ log₂(n) + 1. Every future prefix_sum is now correct. ``` একটা symmetry, যেটা উপভোগ করার মতো: **query lowbit বিয়োগ করে (0-র দিকে হাঁটে), update lowbit যোগ করে (n-এর দিকে হাঁটে)।** এই দুই হাঁটা একে অপরের complementary block-পরিবার ঘুরে আসে, আর সবসময় একমত থাকে। ## 6. দুটো prefix call থেকে range sum কারণ sum invertible (subtraction addition-কে undo করে): ```python def range_sum(l, r): # sum of elements l..r (1-indexed, inclusive) return prefix_sum(r) - prefix_sum(l - 1) ``` এই inversion step-টাই আসল কারণ — plain Fenwick sum আর count পারে, কিন্তু *arbitrary range*-এর **min/max পারে না** — minimum-কে "বিয়োগ করে সরানো" যায় না। ## 7. O(n)-এ build Naive build n বার `add` call করে: O(n log n) — প্রায় সবসময়ই যথেষ্ট। O(n) trick: `tree[i] = a[i]` set করো, তারপর প্রতিটা value-কে তার immediate parent block-এ ঠেলে দাও: ```python for i in range(1, n + 1): tree[i] += a[i] parent = i + (i & (-i)) if parent <= n: tree[parent] += tree[i] ``` ## 8. Fenwick vs segment tree — এই table দিয়ে বেছে নাও | প্রশ্ন | Fenwick (BIT) | Segment tree | | --- | --- | --- | | Code length | ~10 লাইন | ~40 লাইন | | Prefix / range **sum**, point update | হ্যাঁ, ideal | হ্যাঁ | | Range **min / max / gcd** query | না (arbitrary range-এ invertible নয়) | হ্যাঁ | | Range updates (lazy propagation) | শুধু limited trick | হ্যাঁ, স্বাভাবিকভাবেই | | "Tree বেয়ে নামার" trick (প্রথম index যেখানে ...) | কষ্টকর | Natural | | Memory | n + 1-টা integer | ~4n-টা integer | | Constant factor / practice-এ speed | ছোট, দ্রুত | বড় | | Indexing convention | 1-indexed (বাধ্যতামূলক) | তোমার পছন্দ | | Counting / order statistics (count of smaller) | চমৎকার | চলে, কিন্তু ভারী | **Rule of thumb:** task যদি হয় point update-সহ sum বা count — Fenwick। তার চেয়ে fancy কিছু — segment tree। Contest-এ সন্দেহ হলে আগে Fenwick: type করতে দ্রুত, ভুল করা কঠিন। ## 9. Classic ব্যবহার: Fenwick tree দিয়ে গোনা BIT-টাকে **value-দের উপর frequency table** হিসেবে দেখো: `add(v, 1)` মানে "আমি value v দেখেছি"; `prefix_sum(v)` মানে "দেখা value-গুলোর কয়টা ≤ v"। Array-টা ডান থেকে বাঁয়ে process করো, আর প্রতিটা element-এর জন্য জিজ্ঞেস করো "ইতিমধ্যে দেখা value-গুলোর কয়টা আমার চেয়ে ছোট?" — এটাই ঠিক [Count of Smaller Numbers After Self](https://leetcode.com/problems/count-of-smaller-numbers-after-self/)। Value বিশাল হলে (10^9 পর্যন্ত), আগে সেগুলোকে rank দিয়ে replace করো (coordinate compression) — তাহলে BIT ছোট থাকে। ## Common pitfalls - Index 0 ব্যবহার করা — infinite loop বা নিঃশব্দে ভুল answer। সবকিছু 1-indexed-এ shift করো। - `add(i, delta)`-কে "element-টাকে v set করো" semantics-এর সাথে গুলিয়ে ফেলা — set করতে হলে আগে `v - current[i]` add করো আর current value-দের একটা পাশের array রাখো। - ভুলে যাওয়া যে `range_sum`-এ লাগে `prefix_sum(l - 1)`, `prefix_sum(l)` নয়। - Range-min task-এ Fenwick-এর দিকে হাত বাড়ানো — কাজ করবে না; segment tree ব্যবহার করো। ## এরপর কোথায় যাবে - Jump-গুলোর পাশাপাশি ছবি: [visual-explanation.md](visual-explanation.md)। - Assert-সহ working code: [implementation.py](implementation.py)। - আরো গভীর theory আর 2D Fenwick: [cp-algorithms on Fenwick trees](https://cp-algorithms.com/data_structures/fenwick.html)।