Noesis
3.4.16 · D5Trees

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

1,816 words8 min read↑ Back to topic

If any term feels unfamiliar, revisit these first: Binary representation of integers, Two's complement representation, Prefix sum array.

True or false — justify

A "block" below means the contiguous range a cell stores: .

Cell always stores alone.
False — it stores the sum of a block of length ending at ; only odd indices (lowbit ) store a single element.
Every element is stored in exactly one Fenwick cell.
False — lives in the chain , so it appears in cells; that redundancy is exactly what makes updates instead of .
Two different cells' blocks can partially overlap without one containing the other.
False — Fenwick blocks are nested: any two either are disjoint or one fully contains the other. This laminar structure is why the query chain never double-counts.
The query loop and the update loop are the same loop with the sign flipped.
True in shape, false in meaning — query does i -= i&-i toward and update does j += j&-j toward ; they walk opposite directions and touch different cell sets.
A Fenwick tree can answer arbitrary range sums in .
True — it computes , two prefix queries, each , so their difference is still .
always equals in one lookup.
False in general — only when is a power of two, since then and its block is ; otherwise needs several cells.
The number of cells visited by equals the number of set bits in .
True — each step strips exactly one set bit, so the visit count is , which is at most .
A Segment tree can do everything a Fenwick tree can, and more.
True — segment trees also handle min/max/gcd and lazy range updates; Fenwick wins only on constant factor, code size, and memory for sum-like invertible operations.
Fenwick trees work for finding the maximum of a prefix, not just the sum.
True but limited — prefix max works because the update chain covers all needed cells; however range max fails and point decreases cannot be undone, unlike sums which are invertible.
The build-by-updates method and the linear build produce identical arrays.
True — both fill with the same block sums; they differ only in cost, vs .

Spot the error

Each line describes buggy reasoning or code; the answer names the bug and the fix.

"I'll store at Fenwick index using 0-based arrays."
Bug — index has , so the update loop never advances and query never starts; shift to 1-based (store at index ).
"For range I return query(r) - query(l)."
Bug — that excludes , since already includes it; the correct form is .
"To go to the next responsible cell in an update I do j -= j&-j."
Bug — subtracting moves toward (that's the query move) and misses parent cells; update must add: j += j&-j.
"Query terminates when i > n."
Bug — the query index only shrinks, so it never exceeds ; the correct stop is i == 0. The j > n guard belongs to the update loop.
"lowbit(i) = i & i, since that isolates the last bit."
Bug — i & i is just ; the isolation trick is i & (-i), using two's-complement negation to keep only the lowest set bit.
"I resize the tree to length (0..n-1) to save one slot."
Bug — a 1-indexed Fenwick tree needs indices , so the array must have size ; length overflows at index .
"After a[3] += 10 I update tree[3] and tree[6] because 6 contains 3."
Bug — the update chain is , not ; cell 's block is and does not contain index . Follow , never a hand-picked "looks bigger" index.
"To set to a new value , I just write tree[j] = v."
Bug — cells hold block sums, not raw values; compute the delta (needing the old value) and call update(j, v - a_j).
"The linear build is for i: tree[i] += tree[i - lowbit(i)]."
Bug — that reads a not-yet-final cell and points the wrong way; the correct push is to the parent: if i+lowbit(i)<=n: tree[i+lowbit(i)] += tree[i].
"Negative deltas aren't allowed, since sums must grow."
Bug — sum is invertible, so update(j, -5) is perfectly valid; it fixes the same cells with a negative increment.

Why questions

Why is the block length of cell chosen to be specifically?
Because it makes blocks nest perfectly by powers of two, so any prefix decomposes into disjoint blocks matching the set bits of — giving coverage with no overlap.
Why does stripping the lowest set bit correctly leave the "remaining prefix"?
Cell covers exactly , so after removing it the still-needed prefix ends at , which is with its lowest set bit cleared.
Why does the update index jump by to find the next affected cell?
The next larger block still containing shares 's left edge but extends further; by the nesting rule its ending index is , so that formula lands exactly on the next responsible cell.
Why do both loops run in rather than ?
Each step changes one bit of the index (clears one on query, adds one carry-chain on update), and a number below has at most bit positions to change.
Why can't index participate in a Fenwick tree?
means the block has zero length and the step size is zero, so no loop makes progress; there is no lowest set bit to strip or climb.
Why does a plain Prefix sum array fail where Fenwick succeeds?
Its prefix values are precomputed, so one element change forces rewriting every later prefix — per update; Fenwick localizes the fix to cells.
Why is valid for range sums?
Prefix sums telescope: subtracting the prefix ending at cancels , leaving exactly .
Why does the linear build only need one left-to-right pass?
Once cell is reached, all elements inside its block have already been folded in, so it is complete and can immediately donate its total to its parent — no cell is revisited.
Why does two's complement make isolate the lowest set bit?
flips every bit above the lowest set bit and preserves that bit, so ANDing with keeps only that single shared bit.
Why is Fenwick often preferred over a Segment tree for pure prefix sums?
Half the memory, a much smaller constant factor, and roughly ten lines of code — for the invertible sum operation the extra generality of a segment tree is unused.

Edge cases

returns what, and why is it well-defined?
It returns — the loop condition i > 0 is false immediately, so the empty prefix sum is , which is exactly what needs when .
What does read?
Just , since , its block is , and stops the loop — a single lookup.
For , why does an update at touch the most cells?
The chain climbs through every power of two, so an odd/low index near the front triggers the longest update path (still only steps).
What happens to the update loop when already equals and is a power of two?
One update to , then stops — the topmost cell covering is the last one touched.
Is a Fenwick tree of size valid?
Yes — index with stores ; both loops run one step, degenerate but correct.
How do you handle an array whose size is not a power of two?
No special handling — cells beyond meaningful blocks simply never get climbed past ; the loops' j <= n and i > 0 guards make non-power-of-two sizes work unchanged.
What if all elements are zero — do the structure and loops still run?
Yes — every cell holds , queries return , and the loop paths are identical; the invariant is about indices, not values.
Can you build a Fenwick tree over negative or floating values?
Yes for anything with an additive inverse (integers, floats); the block-sum logic never assumes non-negativity, only that addition and subtraction are exact enough.
What is when (out of range)?
Undefined behavior — the query loop may read uninitialized or out-of-bounds cells; always clamp before querying.
Why does a single point update at the last index still cost and not ?
Even may have small lowbit (e.g. climbs ), so worst-case the chain length depends on 's bit pattern, bounded by .
Recall One-sentence self-test

If you can explain why query subtracts lowbit while update adds it and why index 0 is forbidden in your own words, you own this topic. Answer ::: Query removes covered blocks (shrinking toward ) while update repairs every enclosing block (growing toward ); index has no lowest set bit, so both loops stall.

Connections