Lowbit

Every explainer draws the binary indexed tree as a tree: nodes, arrows, i += i & -i written beside them like an incantation. The arrows are not the interesting object. The interesting object is which slice of the array each cell is responsible for, and it is completely determined by one number:

tree[i] = sum of a over (i − lowbit(i), i],    lowbit(i) = i & −i

Cell 13 owns a run of length 1. Cell 12 owns 4. Cell 8 owns 8. Draw those runs at their real positions instead of as a tree, and both algorithms stop being index arithmetic and turn into geometry you can point at.

Four layers, top to bottom:

• The array. a[1..n], the thing everything else is about. In update mode you click a column here; in query mode the columns the answer covers are tinted.
• The tiling strip. A four-pixel bar under the index axis where every run the current operation has reached paints its own span. It is the invariant made visible by never being seen broken: a prefix query fills [1..k] left-edge to right-edge with no gap and no double-paint, because the runs it picks are disjoint and exhaustive by construction. Watch it fill and the proof is the picture.
• The staircase. One row per run length — 1, 2, 4, 8, 16 — with each cell drawn over the columns it covers, labelled with its index and its stored total. Level 0 holds only odd indices, because only odd indices own a run of one. That comb shape is the data structure.
• The readout. The decomposition as arithmetic, plus the binary of k with its set bits lit, plus what a plain scan would have cost. 13 = 01101₂ → 8 + 4 + 1, three runs, and the three runs on screen are exactly those lengths. That correspondence is the whole trick, and once you have seen it the code is obvious rather than memorised.

Query mode. Click a column for prefix(k): the descent k → k − lowbit(k) lights one run per step, each step clearing the lowest set bit, so the number of cells touched is popcount(k) — not “about log n”, exactly the number of ones in the index you asked for. Drag across columns instead and you get a range, drawn as prefix(r) − prefix(l−1): the subtracted runs come up red and paint over the teal in the tiling strip, which is what cancellation looks like.

Update mode. Click a column to add δ to it and the climb i += lowbit(i) lights every run that contains that index, one cell at a time, the stored totals changing as the climb reaches them. The dashed guide line down the column is the reason the set is what it is: those are the only runs the column is inside, so those are the only cells that can be wrong.

The counters are the argument

Three ways to answer “sum of a prefix, with updates”:

The meters under the demo count cells touched, tallied over everything you do — every click, plus a 200-op batch from run 200 ops with a queries/updates dial. Push the dial to 100% and the prefix-sum array wins by a mile; push it to 0% and the plain array does. Anywhere in between, both of them lose to the structure that is worse than each of them at the thing that one is best at. That is the entire case for the Fenwick tree and it is not an asymptotics claim — it is two bars on a screen, from a workload you chose.

Controls: n is 8, 16 or 32; δ is the update amount (negative is allowed); q/u switch modes, ←/→ move the caret, space applies, r reshuffles the array, w runs a batch.

Reuse

src/lowbit.js is a framework-free ES module, no rendering and no timers:

• lowbit(i) — i & -i; popcount(x).
• span(i) — { i, len, from, to, level }, the run cell i owns.
• layout(n) / levels(n) — every span, and how many rows they stack into.
• build(values) — the 1-indexed tree in O(n) (seed each cell, then push each into its parent left to right).
• prefixPath(k) / updatePath(i, n) — the two walks as index lists.
• prefixSum(tree, k) — { total, steps } with each step’s span, value and running total; rangeSum(tree, l, r) — { total, add, sub }.
• applyUpdate(tree, n, i, delta) — mutates, returns the climb.
• bruteForce(values, l, r) — the oracle.
• opCost(op, n) / race(ops, n) — cells touched by all three structures, for one op and for a workload.
• randomValues, randomOps(count, n, queryShare), bitsOf(k, width).

Gotchas

• Everything is 1-indexed. tree[0] is unused and prefixPath(0) is empty, which is exactly what makes rangeSum(tree, 1, r) fall out for free — the subtracted half is a walk of zero steps rather than a special case.
• lowbit relies on two’s complement over 32-bit ints, so i must be a positive int32. span() throws below 1; above 2³¹ the bit trick is not the thing that breaks first.
• The tree stores sums of ranges, not elements. tree[i] equals a[i] only when i is odd. Reading a single element back means prefix(i) − prefix(i-1), which is why the structure is a poor fit when you mostly want point reads.
• build is O(n), not n calls to applyUpdate — the difference is n log n versus n, and the loop is three lines either way.
• opCost charges the prefix-sum array n − i + 1 for an update, which is the honest cost of keeping it correct; implementations that batch or defer are a different structure and should be counted as one.
• The demo bundles its own copy of lowbit.js (self-contained by contract); re-copy after editing src/.