Problem link ও উৎস
- **Original source:** self-exercise (এই folder-এর `fenwick-tree.md`-এর walkthrough)
- **Platform:** self-exercise — কোনো judge নেই, ইচ্ছে করেই
- **Topic:** segment tree and fenwick tree
- **Difficulty:** Easy
- **Pattern:** lowbit navigation (index-jump hand-tracing)
- **Basic idea inherited from:** bit manipulation — math level 4 (`i & (-i)` = lowest set bit)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
এটাও judge problem নয় — একটা **hand-tracing exercise** Fenwick tree (Binary Indexed Tree)-র জন্য। `n = 16`-এ দুটো operation হাতে trace করো, প্রতিটা **visited index লিখে রেখে**:
```text
1) prefix_sum(13): কোন কোন tree-index ছুঁই, কোন order-এ?
2) add(5, +10): element 5-কে ধারণ করা কোন কোন index ছুঁই?
```
মূল চাবি: `lowbit(i) = i & (-i)` — query এটা **বিয়োগ** করে 0-র দিকে হাঁটে, update এটা **যোগ** করে n-এর দিকে হাঁটে।
### Input ও output {#8-example-input-and-output}
```text
n = 16, প্রথমে প্রতিটা element i ধরে রাখে value i (a = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16])
prefix_sum(13) = 13 * 14 / 2 = 91
visited tree indices: 13, 12, 8
add(5, +10) করার পর:
prefix_sum(4) = 10 (element 5-এর আগে: অপরিবর্তিত)
prefix_sum(5) = 25 (আগে 15, এখন 15 + 10)
prefix_sum(16) = 136 + 10 = 146 (আগে 16*17/2 = 136)
touched tree indices: 5, 6, 8, 16
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা লম্বা সিঁড়ি, যেখানে কিছু ধাপে "চেকপয়েন্ট" বসানো — কোনোটা ছোট অংশের হিসাব রাখে, কোনোটা বড়। উপর থেকে নিচে নামতে (prefix_sum) তুমি বড় বড় লাফে কাছের চেকপয়েন্টগুলো ছুঁয়ে যাও, যতক্ষণ না নিচে পৌঁছাও। কিছু বদলালে (add) তুমি উল্টো দিকে উঠে সব বড় চেকপয়েন্টকে খবর দাও যাদের হিসাবে এই ধাপটা ধরা আছে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা **bit manipulation**-এর উপর দাঁড়িয়ে — ঠিক সেই `i & (-i)` lowest-set-bit trick যেটা তুমি math level 4-এ দেখেছ। Fenwick tree হলো সেই জায়গা যেখানে এই bit trick তার আসল দাম আদায় করে: এটাই navigation-এর পুরো engine।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: **index `i` দায়ী `i`-তে শেষ হওয়া শেষ `lowbit(i)`-টা element-এর জন্য**। two's complement-এ `-i` মানে `i`-র সব bit flip করে 1 যোগ — ফলে ঠিক lowest set bit-টা `i`-র সাথে মেলে, বাকি সব 0। তাই `i`-র binary form-ই tiling plan: প্রতিটা set bit একটা করে block দেয়।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **Fenwick tree** — `n+1` ঘরের একটা flat array, **1-indexed**। Index 0 কখনো ব্যবহার হয় না, কারণ `lowbit(0) = 0` আর loop চিরকাল ঘুরত।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
এই exercise-এর লক্ষ্য hop-গুলো হাতে অনুভব করা: prefix-query কীভাবে last set bit ঝেড়ে বাঁয়ে লাফায়, আর update কীভাবে lowbit যোগ করে ডানে covering block-গুলোয় যায়। এই দুই হাঁটা একে অপরের পরিপূরক block-পরিবার ঘুরে আসে, তাই সবসময় একমত থাকে — এটা না বুঝলে BIT চিরকাল জাদু মনে হবে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: Fenwick ছাড়া, একটা plain array-তে loop চালিয়ে `1..i` যোগ করা, আর update-এ সরাসরি `a[i]` বদলানো।
```text
prefix_sum(13): s = 0; for i in 1..13: s += a[i] -> 13-টা পড়া
add(5, +10): a[5] += 10 -> O(1) এখানে
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
plain array-তে prefix_sum প্রতিবার O(n)। আর prefix-sum **array** রাখলে update O(n) হয়ে যায় (পরের সব entry stale — দেখো [../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/](../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/README.md))। দুটো একসাথে দ্রুত পাওয়া যায় না plain array-তে। Fenwick দুটোকেই **O(log n)**-এ নামায়: hop-সংখ্যা = সেট bit-সংখ্যা ≤ log₂n।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **hop-সংখ্যাই log n-এ বাঁধা**। `prefix_sum(i)` ঠিক ততবার লাফায় যত `i`-তে set bit আছে; `add(i, ...)` ঠিক ততবার যত covering block আছে — দুটোই ≤ log₂n + 1। তাই কোনো scan ছাড়াই, শুধু কয়েকটা strategic index ছুঁয়ে কাজ শেষ।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
দুটো ছোট loop মুখস্থ করো: query-তে `i -= i & (-i)` (0-তে না পৌঁছানো পর্যন্ত), update-এ `i += i & (-i)` (n ছাড়ানো পর্যন্ত)। এই দুই hop-প্যাটার্ন একে অপরের পরিপূরক block-গুলো ছোঁয়, তাই যেকোনো update-এর পর প্রতিটা prefix_sum সঠিক থাকে — কোনো rebuild ছাড়াই।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** prefix-sum array "একটা update-এ পরের সব ভেঙে দেয়" — এই সমস্যাকে এড়াতে ভাবো "প্রতিটা index পুরো prefix না রেখে শুধু একটা ছোট block রাখুক, block-size = lowbit(i)।" তখন একটা update মাত্র কয়েকটা block-কে ছোঁয়, আর prefix কয়েকটা block জুড়ে তৈরি হয়। এই একটা মোচড়ই prefix sums-কে update-সহ্য করে তোলে।
### ছবিতে বোঝা {#7-visual-explanation}
`n = 16`-এ index-jump trace। `prefix_sum(13)` বাঁয়ে নামে (lowbit বিয়োগ), `add(5)` ডানে ওঠে (lowbit যোগ):
```text
prefix_sum(13): strip lowest set bit each step
13 = 1101₂ -> take tree[13] (covers 13..13); 13 - 1 = 12
12 = 1100₂ -> take tree[12] (covers 9..12); 12 - 4 = 8
8 = 1000₂ -> take tree[8] (covers 1..8); 8 - 8 = 0 -> stop
visited: 13 -> 12 -> 8 (3 hops = set bits of 13)
blocks: [13..13] + [9..12] + [1..8] = exactly 1..13, no gaps
add(5, +10): add lowest set bit each step (n = 16)
5 = 0101₂ -> tree[5] += 10 (block 5..5 has 5); 5 + 1 = 6
6 = 0110₂ -> tree[6] += 10 (block 5..6 has 5); 6 + 2 = 8
8 = 1000₂ -> tree[8] += 10 (block 1..8 has 5); 8 + 8 = 16
16 = 10000₂ -> tree[16] += 10 (block 1..16 has 5); 16 + 16 = 32 > 16 -> stop
visited: 5 -> 6 -> 8 -> 16 (4 entries touched)
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`prefix_sum(13)` (a = [1..16]):
1. `i = 13`, `s += tree[13]` (block 13..13)। `lowbit=1`, `i = 12`।
2. `i = 12`, `s += tree[12]` (block 9..12)। `lowbit=4`, `i = 8`।
3. `i = 8`, `s += tree[8]` (block 1..8)। `lowbit=8`, `i = 0` → থামো।
4. block-গুলো: `[1..8] + [9..12] + [13..13]` = `1..13`, ফাঁক নেই।
5. মান = `(1+...+8) + (9+...+12) + 13 = 36 + 42 + 13 = 91`। ✓
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
class Fenwick:
"""Fenwick tree (BIT): update-সহ prefix sums, 1-indexed।
Navigation-ই পুরো magic:
query নামে: i -= i & (-i) (lowest set bit ছাঁটো)
update ওঠে: i += i & (-i) (পরের covering block-এ লাফাও)
Index i দায়ী i-তে শেষ হওয়া lowbit(i)-টা element-এর জন্য।"""
def __init__(self, n):
self.n = n
self.tree = [0] * (n + 1) # slot 0 অব্যবহৃত
def add(self, i, delta): # element i += delta
assert 1 <= i <= self.n, "Fenwick is 1-indexed"
while i <= self.n:
self.tree[i] += delta
i += i & (-i) # পরের covering block
def prefix_sum(self, i): # sum of elements 1..i
s = 0
while i > 0:
s += self.tree[i]
i -= i & (-i) # lowest set bit ছাঁটো
return s
# hand-trace-এর জন্য: visited index-গুলো ফেরত দাও (verify করার সুবিধায়)
def query_path(self, i):
path = []
while i > 0:
path.append(i)
i -= i & (-i)
return path
def update_path(self, i):
path = []
while i <= self.n:
path.append(i)
i += i & (-i)
return path
# ---- tests ----
fw = Fenwick(16)
for i in range(1, 17):
fw.add(i, i) # element i ধরে রাখে value i
# হাতে বের করা visited path-গুলো মিলিয়ে দেখা
assert fw.query_path(13) == [13, 12, 8] # prefix_sum(13)-এর hops
assert fw.update_path(5) == [5, 6, 8, 16] # add(5,...)-এর touched indices
# মান-ও সঠিক, brute force-এর সাথে মেলানো
assert fw.prefix_sum(13) == sum(range(1, 14)) # 91
fw.add(5, 10) # 5,6,8,16 ছোঁয়
assert fw.prefix_sum(4) == 10 # element 5-এর আগে: অপরিবর্তিত
assert fw.prefix_sum(5) == 15 + 10 # 25
assert fw.prefix_sum(16) == sum(range(1, 17)) + 10
# brute force-এর সাথে exhaustively সব prefix যাচাই
ref = list(range(0, 17)) # ref[i] = original value at i
ref[5] += 10
for i in range(0, 17):
assert fw.prefix_sum(i) == sum(ref[1:i + 1])
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `self.tree = [0]*(n+1)` — slot 0 অব্যবহৃত (1-indexed বাধ্যতামূলক)।
- `add`: `i += i & (-i)` দিয়ে element `i`-কে ধারণ করা প্রতিটা block-এ delta ঠেলে।
- `prefix_sum`: `i -= i & (-i)` দিয়ে block-গুলো জুড়ে `1..i` বানায়।
- `query_path` / `update_path` — শুধু hand-trace যাচাইয়ের জন্য visited index-এর তালিকা ফেরত দেয়।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`Fenwick(16)`-এ element `i` ধরে value `i`। `query_path(13)` দেয় `[13,12,8]`, `update_path(5)` দেয় `[5,6,8,16]` — হাতের trace-এর সাথে হুবহু মেলে। `prefix_sum(13)=91`; `add(5,10)`-এর পর `prefix_sum(5)=25` কিন্তু `prefix_sum(4)=10` অপরিবর্তিত। সব assert pass। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**add O(log n)** আর **prefix_sum O(log n)** — hop-সংখ্যা ≤ log₂n + 1। Build (n বার add) O(n log n)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — `n+1` ঘরের একটা array।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- Index 0 ব্যবহার করা — `lowbit(0)=0`, infinite loop বা নিঃশব্দ ভুল। সব 1-indexed-এ shift করো।
- query-তে `+=` আর update-এ `-=` গুলিয়ে ফেলা — দিক উল্টে গেলে সব ভুল।
- `add(i, delta)`-কে "set to v" ভাবা — set করতে আগে `v - current[i]` add করো, একটা পাশের array-তে current রেখে।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: math level 4-এর `i & (-i)` lowest-set-bit trick। গভীর treatment [../fenwick-tree.md](../fenwick-tree.md) section 2–6, ছবি [../visual-explanation.md](../visual-explanation.md) section 5–6, runnable code [../implementation.py](../implementation.py)।
### পরের অনুশীলন {#22-similar-harder-problems}
- Dynamic Range Sum Queries (এই BIT দিয়ে range sum + update) —