In a Fenwick tree, why does stripping index i's lowest set bit walk exactly one prefix?

## What each node owns A Fenwick tree (also called a binary indexed tree) over a series of length n uses a companion array of n entries, indexed from 1. Entry `i` does **not** store position `i`'s value and does **not** store the prefix up to `i`. It stores the aggregate of a *block*: the `lowbit(i)` positions ending at `i`, written as the half-open range `(i - lowbit(i), i]`. `lowbit(i) = i & (-i)` isolates the lowest set bit of `i`. Under two's-complement negation, `-i` is `~i + 1`, which leaves the lowest set bit in place and flips everything above it, so the bitwise AND keeps exactly that one bit. Concretely: | i | binary | lowbit | block covered | |---|---|---|---| | 1 | 0001 | 1 | position 1 | | 6 | 0110 | 2 | positions 5–6 | | 8 | 1000 | 8 | positions 1–8 | | 12 | 1100 | 4 | positions 9–12 | | 13 | 1101 | 1 | position 13 | So blocks come in power-of-two sizes, and which size a node gets is dictated by the binary spelling of its own index. Odd indices own a single position; the highest power of two ≤ n owns the entire first half. ## Why the descent tiles the prefix To get the aggregate of `1..i`, start with `i` and repeatedly take the node's value and strip the low bit: - Node `i` covers down to `i - lowbit(i) + 1`. - Everything strictly below that is still missing, and the largest missing index is `i - lowbit(i)`. - So jump there. That is exactly what `i = i - (i & (-i))` does. The blocks therefore abut perfectly: no position is counted twice, none is skipped. **Walk it on 13** (binary 1101): 1. `i = 13`, lowbit 1 → node 13 covers position 13. Jump to 12. 2. `i = 12` (1100), lowbit 4 → node 12 covers positions 9–12. Jump to 8. 3. `i = 8` (1000), lowbit 8 → node 8 covers positions 1–8. Jump to 0, stop. Three nodes: 1 + 4 + 8 = 13 positions, exactly the prefix. And three is precisely the number of 1-bits in 13 — because each step clears one. That is the complexity bound: **the query visits popcount(i) nodes, at most ⌊log₂ n⌋ + 1**. The binary expansion of `i` *is* the decomposition of the prefix into blocks. ## The update walks the other way Adding a delta at position `i` must repair every node whose block contains `i`. Those are found by `i = i + lowbit(i)`, repeated while `i ≤ n`. From position 5: 5 → 6 → 8 → 16 → … Each step moves to the next node upward whose block swallows the previous one, and there are again at most log n of them. It is worth noticing the asymmetry — descending strips bits, ascending adds them — and that neither loop involves comparisons, pointers, or recursion. ## Range queries, and the requirement hiding in them A Fenwick tree natively answers *prefixes*. An arbitrary range `l..r` is answered by `prefix(r) - prefix(l-1)`. That subtraction is not free: it demands that the aggregate operation be **invertible**. Sums qualify; so do bitwise XOR and counts. Minimum and maximum do not, which is why an arbitrary range-minimum query is not something a plain Fenwick tree can serve. ## Practical notes - **1-indexing is structural, not stylistic.** `lowbit(0)` is 0, so a 0 index would loop forever on the update path and terminate instantly on the query path. Series positions are mapped to `1..n`. - **Space is n words** — no child pointers, no padding to a power of two, roughly a quarter to a half of what a segment tree's array layout takes. - **A linear build exists.** Rather than n separate updates costing O(n log n), fill the array with the raw values and then, for each `i` ascending, push `tree[i]` into `tree[i + lowbit(i)]` when that index is in range. One pass, O(n). - **The failure mode is silent.** Reverse a direction — strip bits on the update or add them on the query — and the structure still returns numbers, just wrong ones, and often right for small indices. Test against a brute-force scan over random operation sequences rather than against hand-picked examples. ## What an interviewer is listening for Not the two loops, which are four lines each and easy to memorise, but the sentence that explains them: *node i covers the lowbit(i) positions ending at i, so stripping the low bit lands on the last position not yet covered.* Everything else — the popcount bound, the perfect tiling, the direction of the update — falls out of that one invariant.