004 — Hand-trace Fenwick Jumps¶

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

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)

প্রশ্ন ও উদাহরণ¶

সহজ করে প্রশ্ন¶

এটাও 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-এর দিকে হাঁটে।

Input ও output¶

উদাহরণ

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

চেনা উদাহরণে বোঝা¶

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

ভিত্তির ধারণা¶

আগের কোন ধারণাটি লাগবে¶

এটা bit manipulation-এর উপর দাঁড়িয়ে — ঠিক সেই i & (-i) lowest-set-bit trick যেটা তুমি math level 4-এ দেখেছ। Fenwick tree হলো সেই জায়গা যেখানে এই bit trick তার আসল দাম আদায় করে: এটাই navigation-এর পুরো engine।

ভেতরের যুক্তি¶

লুকানো 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 দেয়।

কী দিয়ে তথ্য রাখব¶

একটা Fenwick tree — n+1 ঘরের একটা flat array, 1-indexed। Index 0 কখনো ব্যবহার হয় না, কারণ lowbit(0) = 0 আর loop চিরকাল ঘুরত।

এটি কেন উপযুক্ত¶

এই exercise-এর লক্ষ্য hop-গুলো হাতে অনুভব করা: prefix-query কীভাবে last set bit ঝেড়ে বাঁয়ে লাফায়, আর update কীভাবে lowbit যোগ করে ডানে covering block-গুলোয় যায়। এই দুই হাঁটা একে অপরের পরিপূরক block-পরিবার ঘুরে আসে, তাই সবসময় একমত থাকে — এটা না বুঝলে BIT চিরকাল জাদু মনে হবে।

ধাপে ধাপে সমাধান¶

প্রথম সরল উপায়¶

প্রথম সরল চিন্তা: 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) এখানে

কোথায় বেশি কাজ হচ্ছে¶

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।

যে বিষয়টি খেয়াল করতে হবে¶

মূল observation: hop-সংখ্যাই log n-এ বাঁধা। prefix_sum(i) ঠিক ততবার লাফায় যত i-তে set bit আছে; add(i, ...) ঠিক ততবার যত covering block আছে — দুটোই ≤ log₂n + 1। তাই কোনো scan ছাড়াই, শুধু কয়েকটা strategic index ছুঁয়ে কাজ শেষ।

আরও কম কাজে সমাধান¶

দুটো ছোট loop মুখস্থ করো: query-তে i -= i & (-i) (0-তে না পৌঁছানো পর্যন্ত), update-এ i += i & (-i) (n ছাড়ানো পর্যন্ত)। এই দুই hop-প্যাটার্ন একে অপরের পরিপূরক block-গুলো ছোঁয়, তাই যেকোনো update-এর পর প্রতিটা prefix_sum সঠিক থাকে — কোনো rebuild ছাড়াই।

ভাবনার পরিবর্তন¶

মোচড়: prefix-sum array "একটা update-এ পরের সব ভেঙে দেয়" — এই সমস্যাকে এড়াতে ভাবো "প্রতিটা index পুরো prefix না রেখে শুধু একটা ছোট block রাখুক, block-size = lowbit(i)।" তখন একটা update মাত্র কয়েকটা block-কে ছোঁয়, আর prefix কয়েকটা block জুড়ে তৈরি হয়। এই একটা মোচড়ই prefix sums-কে update-সহ্য করে তোলে।

ছবিতে বোঝা¶

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)

ছোট input-এ ধাপে ধাপে¶

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

কোড ও ব্যাখ্যা¶

Python¶

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!")

কোডের প্রতিটি অংশ¶

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 মিলিয়ে দেখা¶

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

খরচ ও সাধারণ ভুল¶

সময়¶

add O(log n) আর prefix_sum O(log n) — hop-সংখ্যা ≤ log₂n + 1। Build (n বার add) O(n log n)।

অতিরিক্ত জায়গা¶

O(n) — n+1 ঘরের একটা array।

যে ভুলগুলো এড়াতে হবে¶

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

শেখা ও পরের অনুশীলন¶

ভিত্তির সঙ্গে সম্পর্ক¶

ভিত্তি: 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।

পরের অনুশীলন¶

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)

কৌশলটি মনে রাখুন¶

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

নিজেকে যাচাই করুন¶

ভবিষ্যতের আমাকে: 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।