004 — Hand-trace Fenwick Jumps¶

Source¶

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)

1. Problem in simple words¶

এটাও judge problem নয় — একটা hand-tracing exercise Fenwick tree (Binary Indexed Tree)-র জন্য। n = 16-এ দুটো operation হাতে trace করো, প্রতিটা visited index লিখে রেখে:

1) prefix_sum(13): কোন কোন tree-index ছুঁই, কোন order-এ?
2) add(5, +10):    element 5-কে ধারণ করা কোন কোন index ছুঁই?

মূল চাবি: lowbit(i) = i & (-i) — query এটা বিয়োগ করে 0-র দিকে হাঁটে, update এটা যোগ করে n-এর দিকে হাঁটে।

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 চিরকাল জাদু মনে হবে।

6. Real-life analogy¶

ভাবো একটা লম্বা সিঁড়ি, যেখানে কিছু ধাপে "চেকপয়েন্ট" বসানো — কোনোটা ছোট অংশের হিসাব রাখে, কোনোটা বড়। উপর থেকে নিচে নামতে (prefix_sum) তুমি বড় বড় লাফে কাছের চেকপয়েন্টগুলো ছুঁয়ে যাও, যতক্ষণ না নিচে পৌঁছাও। কিছু বদলালে (add) তুমি উল্টো দিকে উঠে সব বড় চেকপয়েন্টকে খবর দাও যাদের হিসাবে এই ধাপটা ধরা আছে।

7. Visual explanation¶

n = 16-এ index-jump trace। prefix_sum(13) বাঁয়ে নামে (lowbit বিয়োগ), add(5) ডানে ওঠে (lowbit যোগ):

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)

8. Example input and output¶

n = 16, প্রথমে প্রতিটা element i ধরে রাখে value i (a = [1,2,...,16])

prefix_sum(13) = 1 + 2 + ... + 13 = 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   (আগে 1+...+16 = 136)
  touched tree indices: 5, 6, 8, 16

9. Brute force thinking¶

প্রথম সরল চিন্তা: Fenwick ছাড়া, একটা plain array-তে loop চালিয়ে 1..i যোগ করা, আর update-এ সরাসরি a[i] বদলানো।

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/)। দুটো একসাথে দ্রুত পাওয়া যায় না 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-সহ্য করে তোলে।

14. Step-by-step dry run¶

prefix_sum(13) (a = [1..16]):

i = 13, s += tree[13] (block 13..13)। lowbit=1, i = 12।
i = 12, s += tree[12] (block 9..12)। lowbit=4, i = 8।
i = 8, s += tree[8] (block 1..8)। lowbit=8, i = 0 → থামো।
block-গুলো: [1..8] + [9..12] + [13..13] = 1..13, ফাঁক নেই।
মান = (1+...+8) + (9+...+12) + 13 = 36 + 42 + 13 = 91। ✓

15. Python solution¶

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-এর তালিকা ফেরত দেয়।

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!।

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 রেখে।

21. Which basic problem this inherits from¶

ভিত্তি: math level 4-এর i & (-i) lowest-set-bit trick। গভীর treatment ../fenwick-tree.md section 2–6, ছবি ../visual-explanation.md section 5–6, runnable code ../implementation.py।

22. Similar harder problems¶

Dynamic Range Sum Queries (এই BIT দিয়ে range sum + update) — https://cses.fi/problemset/task/1648 (এই tracker-এর #6)
Count Inversions (BIT কে frequency table হিসেবে) — self-exercise (#10)
Count of Smaller Numbers After Self (BIT over values) — https://leetcode.com/problems/count-of-smaller-numbers-after-self/ (#13)

23. Pattern learned¶

Lowbit navigation: i & (-i) দিয়ে BIT-এ চলা — query last set bit ঝেড়ে বাঁয়ে, update lowbit যোগ করে ডানে। এই hop-প্যাটার্ন BIT-এর সব ব্যবহারের (sum, count, order statistics) মূল engine।

24. Final summary¶

ভবিষ্যতের আমাকে: BIT মানেই lowbit hop। i-র binary form-ই বলে দেয় কোন block ছোঁব। query বিয়োগ করে নামে, update যোগ করে ওঠে — এই দুই হাঁটা সবসময় একমত। এই trace (section 7) চোখ বন্ধ করে করতে পারা চাই; তাহলে #6, #10, #13 সব স্রেফ এই hop-এর উপর variation।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।