Fenwick Tree
01 / The one-sentence essence
A 1-indexed array where each cell holds the sum of a power-of-two-sized range — the range length is the lowest set bit of the index. Point updates walk up the implicit tree by adding the lowest set bit; prefix sums walk down by subtracting it. Both in O(log N), in ten lines of code, with no tree to allocate.
Problemprefix sum + point updateInput[3,2,-1,6,5,4,-3,3]Updatearr[5] += 10Query[2,7]
Array of length 8 (1-indexed). The Fenwick tree bit[i] will store the sum of lowbit(i) cells ending at i.
step
0 / 22
phase
build
live
—
0 / 22
02 / The pattern signature
# 1-indexed BIT, length Ndef lowbit(i): return i & -i# point update: arr[i] += deltadef update(i, delta):while i ≤ N:bit[i] += deltai += lowbit(i)# prefix sum of arr[1..i]def prefix(i):s ← 0while i > 0:s += bit[i]; i −= lowbit(i)return s# range sum [l..r] = prefix(r) − prefix(l − 1)
03 / When to recognize this pattern
"range sum with point updates"
The canonical use case. Same problem class as Segment Tree, but BIT is shorter, faster in practice, and uses half the memory. Pick BIT first when sum (or any easily-invertible aggregate) is all you need.
"count smaller / inversions / coordinate compression"
Sweep the array, coordinate-compressing values into a small index space, then maintain a frequency BIT. Each new value contributes a prefix-count query before it's inserted. LC 315, 493, 327 — all the same recipe.
"range update + point query"
A BIT on the difference array.
update(l, +δ), update(r+1, −δ), then prefix(i) reads the current value at i. Saves a Segment Tree with lazy propagation when point queries are enough."2-D BIT for range sum over a grid"
Two nested while-loops (one per dimension) give an O(log² N) range-sum-rectangle on a mutable grid. LC 308.
04 / Common pitfalls
i.
0-indexed vs 1-indexed.
BIT is naturally 1-indexed — index 0 has no
lowbit (the loop never advances) and acts as the recursion terminator for prefix queries. Trying to use 0 as a valid array index breaks both walks. Allocate bit[0..N] and start indices at 1.ii.
Reaching for Segment Tree when BIT would do.
BIT covers sum and any aggregate with an inverse (sum, XOR, count). For min / max / gcd you need Segment Tree because they aren't invertible — there's no subtract-to-undo. Don't default to the heavier structure when the simpler one works.
iii.
Forgetting the difference-array trick for range updates.
Naïve BIT only does point update + range query. The classic mistake is rebuilding the whole BIT for range updates. The fix is to BIT the difference array:
update(l, +δ); update(r+1, −δ), then prefix(i) is the value at i. Two range updates per call, O(log N) total.05 / Go practice — on LeetCode
Four problems, ordered by difficulty. No solutions here, by design.