Fenwick Tree (Binary Indexed Tree) — Update সহ্য করা Prefix Sums¶

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।

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 করে:

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 করো।

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-সহ:

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 যোগ করে:

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:

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 করে):

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-এ ঠেলে দাও:

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। 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।
Assert-সহ working code: implementation.py।
আরো গভীর theory আর 2D Fenwick: cp-algorithms on Fenwick trees।