Fenwick tree (Binary Indexed Tree) — prefix sums, O(log n) update and query

3.4.16 · Coding › Trees

WHY yeh structure exist karta hai?

WHAT har cell mein stored hai? (lowbit insight)

Values $a_{1}, a_{2}, \dots, a_{n}$ ke ek array ke liye (1-indexed), Fenwick cell define karo

$tree [i] = \sum_{k = i - lowbit (i) + 1}^{i} a_{k}$

jahan == $lowbit (i) = i & (- i)$ == $i$ ke lowest set bit ki value hai.

Toh cell $i$ index $i$ par khatam hone wale $lowbit (i)$ elements ka sum store karta hai.

$i$	binary	lowbit	$a_{k}$ cover karta hai $k \in$ ke liye
1	0001	1	[1,1]
2	0010	2	[1,2]
3	0011	1	[3,3]
4	0100	4	[1,4]
5	0101	1	[5,5]
6	0110	2	[5,6]
7	0111	1	[7,7]
8	1000	8	[1,8]

Figure — Fenwick tree (Binary Indexed Tree) — prefix sums, O(log n) update and query

HOW: query ko scratch se derive karna

Hum chahte hain $prefix (i) = a_{1} + a_{2} + \dots + a_{i}$ .

Step 1. Cell $i$ humein already last block deta hai: $\sum_{k = i - lowbit (i) + 1}^{i} a_{k}$ . Kyun? Yeh literally iska definition hai.

Step 2. Jo bacha hai woh hai $prefix (i - lowbit (i))$ — us block se pehle wala part. Kyun? Lowbit-sized chunk hataane ke baad humein ek chhote index tak prefix chahiye hoti hai.

Step 3. Recurse karo: $tree [i]$ add karte raho aur lowest bit strip karte raho jab tak $i = 0$ na ho jaye. Yeh jaldi terminate kyun hota hai? Har step $i$ se ek set bit remove karta hai, toh yeh zyada se zyada (set bits ki sankhya) $\leq lo g_{2} n$ baar run karta hai.

$prefix (i) = \sum tree [i], i \leftarrow i - lowbit (i) until i = 0$

def query(tree, i):          # prefix sum a[1..i]
    s = 0
    while i > 0:
        s += tree[i]
        i -= i & (-i)        # strip lowest set bit
    return s

HOW: update ko scratch se derive karna

$a_{j}$ mein $δ$ add karne ke liye har us cell ko fix karna hoga jiske block mein index $j$ hai.

Step 1. Cell $j$ mein $a_{j}$ hai (uska block $j$ par khatam hota hai). Wahaan $δ$ add karo. Step 2. Agla cell jo $j$ contain karta hai woh index $j + lowbit (j)$ par hai. Kyun? Agla bada block jo $j$ ko include karta hai usi left edge se start hota hai lekin aage tak extend karta hai; uska index $j$ plus uska apna lowbit hai, jo in blocks ki nesting structure ke according $j + lowbit (j)$ ke barabar hai. Step 3. Repeat karo jabtak $j \leq n$ .

$update: tree [j] + = δ, j \leftarrow j + lowbit (j) until j > n$

def update(tree, n, j, delta):   # a[j] += delta
    while j <= n:
        tree[j] += delta
        j += j & (-j)            # go to next responsible cell

Range sum $[l, r]$ sirf $query (r) - query (l - 1)$ hai.

Worked examples

Common mistakes

Complexity

Linear build (80/20 trick): tree[i] = a[i] initialize karo, phir $i$ ke liye 1 se $n$ tak, apna block sum apne parent mein push karo: if i+lowbit(i) <= n: tree[i+lowbit(i)] += tree[i]. Kyun? Har cell pehle complete hoti hai, phir apna block agla responsible cell ko donate karti hai — ek pass, $O (n)$ .

Fenwick cell tree[i] kya store karta hai?

a[i-lowbit(i)+1 .. i] ka sum, length lowbit(i) ka ek block jo i par khatam hota hai.

lowbit(i) kaise compute karte hain?

i & (-i), lowest set bit ki value (two's-complement negation use karta hai).

Query (prefix sum) loop direction?

tree[i] add karo, phir i -= i & (-i), jab tak i == 0 (NEECHE jaao).

Update (point add) loop direction?

tree[j] mein delta add karo, phir j += j & (-j), jabtak j <= n (UPAR jaao).

Update aur query ki time complexity?

Dono

O (lo g n)

, kyunki har step index ka ek bit change karta hai.

Range sum [l, r] kaise milega?

query(r) - query(l-1).

Fenwick tree 1-indexed kyun honi chahiye?

lowbit(0)=0, toh index 0 par loops kabhi progress nahi karte; index 0 ka koi lowest set bit nahi hai.

Kisi given element index j ko kitni cells contain karti hain?

O (lo g n)

— chain j, j+lowbit(j), ... n tak.

O(n) build trick kya hai?

tree[i]=a[i]; phir har i ke liye, if i+lowbit(i)<=n: tree[i+lowbit(i)] += tree[i].

Plain prefix-sum array ki weakness jo Fenwick fix karta hai?

O (n)

per update; Fenwick update ko

O (lo g n)

karta hai fast queries rakhte hue.

Recall Feynman: ek 12-saal ke bachche ko explain karo

Socho ek row mein numbered boxes hain. Har box se ek-ek karke total maangne ki jagah (slow), kuch special boxes apne pehle wale boxes ke ek chunk ka running subtotal rakhte hain. Chunk size ek number trick se decide hoti hai: box ke number ko binary mein likhkar sabse daayein wali 1 dekho — woh batata hai woh box kitne boxes summarize karta hai. "Box 6 tak total" paane ke liye, tum sirf do-teen subtotal boxes visit karte ho aur unhe add karte ho — jaise ek-ek candy ginne ki jagah do pre-packed bundles utha lena. Ek candy count change karne ke liye, tum sirf un thodi bundles fix karte ho jo use contain karti hain. Dono taraf: sirf muthi bhar steps, kabhi poori row nahi.

Connections

Prefix sum array — $O (1)$ -query, $O (n)$ -update baseline jo Fenwick improve karta hai.
Segment tree — zyada general (koi bhi associative op, range updates), lekin heavy; Fenwick sums ke liye lean special case hai.
Two's complement representation — isliye i & -i lowest set bit isolate karta hai.
Binary representation of integers — set bits = query/update steps ki sankhya.
Inversion counting / Order statistics — classic Fenwick applications.
Range update with difference array — range-update/point-query ke liye BIT ke saath combine karo.