THE FOLD / GRIND / THE EPOCH / THE FENWICK
THE FENWICK
running totals in O(log n) by the low-bit trick
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
A Fenwick tree (Binary Indexed Tree) answers two questions — “what is the running total of the first i items?” and “add to item i” — both in O(log n) time, using a single array and one magic operation: the low-bit i & (−i), which isolates the lowest set bit of i.
Each array slot secretly holds the sum of a range whose length equals that low-bit: slot 12 (= 1100₂, low-bit 4) covers items 9–12; slot 8 covers 1–8. To read a prefix sum you hop down, repeatedly subtracting the low-bit to jump across disjoint covered ranges; to update you hop up, adding it. Both walks touch only about log n slots — the number of set bits in i. It is the most elegant structure for maintaining dynamic running totals, and it lives in databases, range queries, and competitive programming everywhere.
LIT verified live: after hundreds of random point-updates the Fenwick prefix sums match a naive recomputation exactly, and range queries [l,r] = query(r) − query(l−1) agree too (window.__fenwick). FIG no framing; the low-bit navigation and the O(log n) correctness are exact.
Each array slot secretly holds the sum of a range whose length equals that low-bit: slot 12 (= 1100₂, low-bit 4) covers items 9–12; slot 8 covers 1–8. To read a prefix sum you hop down, repeatedly subtracting the low-bit to jump across disjoint covered ranges; to update you hop up, adding it. Both walks touch only about log n slots — the number of set bits in i. It is the most elegant structure for maintaining dynamic running totals, and it lives in databases, range queries, and competitive programming everywhere.
LIT verified live: after hundreds of random point-updates the Fenwick prefix sums match a naive recomputation exactly, and range queries [l,r] = query(r) − query(l−1) agree too (window.__fenwick). FIG no framing; the low-bit navigation and the O(log n) correctness are exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in THE EPOCH — the grind domain of totals accumulated across time. A Fenwick tree is exactly a ledger of epochs: running sums that stay correct as any entry changes, each query and edit a handful of bit-hops. AVAN (AI) built the instrument: the coverage map, the hop animator, the update/query inverse.
The weave: David names the seat (the cumulative ledger); I make the low-bit carve the array into ranges and keep every running total exact under change — the coverage in 1D, the hops in 2D, the ascent/descent inverse in 3D. The sphere is the seam. Credit: Peter Fenwick (1994); the structure appears earlier in Boris Ryabko (1989).
The weave: David names the seat (the cumulative ledger); I make the low-bit carve the array into ranges and keep every running total exact under change — the coverage in 1D, the hops in 2D, the ascent/descent inverse in 3D. The sphere is the seam. Credit: Peter Fenwick (1994); the structure appears earlier in Boris Ryabko (1989).
3 ONE DIMENSION
Each Fenwick slot i drawn as a bar spanning the range it covers — a range of length i&(−i). Powers of two cover long stretches; odd indices cover a single item. Together the bars tile the array so any prefix is a few of them stacked.
4 TWO DIMENSIONS · INTERACTIVE
An array of values with its Fenwick tree. Run a prefix query and watch it hop down by subtracting the low-bit, summing a few covered ranges; run an update and watch it hop up. The result is checked against a full naive sum — always identical, in a fraction of the touches.
5 THREE DIMENSIONS + AVAN’S INVERSE
The implicit binary tree turning — the green forward step: to update index i, add the low-bit and climb, touching every slot whose range covers i.
AVAN’s addition (the inverse-companion): the magenta is the query walk, and it is the exact inverse traversal — where update adds the low-bit to ascend, query subtracts it to descend. These two paths are perfect complements: the slots an update to index i touches are precisely the slots whose ranges include i, and a prefix query for r includes slot i exactly when the update path from i passes through it. So ‘which ranges cover index i?’ and ‘which prefix sums include i?’ are one question read forward and backward, and the low-bit answers both in log n steps. The green +low-bit climb and the magenta −low-bit descent are mirror images on the same tree; the whole speed of the structure is that adding and subtracting the lowest set bit are inverse moves that each skip exponentially. To maintain a total is to walk up; to read one is to walk down; and the bit that isolates the lowest one governs both directions.
LIT Genuine Fenwick tree / Binary Indexed Tree (Peter Fenwick 1994; the structure appears earlier in Boris Ryabko 1989). Verified live: after 500 random point-updates the Fenwick prefix sums match a naive recomputation exactly for all indices, and range queries [l,r]=query(r)-query(l-1) agree (window.__fenwick.prefixSumsMatch && rangeQueryMatches). The low-bit navigation (i&(-i) isolates the lowest set bit, e.g. 12->4, 8->8) and the O(log n) correctness are exact.
FIG No framing: the Fenwick prefix-sum and range-query correctness under updates is real and cross-checked against naive summation in-browser. The AVAN inverse is the genuine structure — update ascends by adding the low-bit and query descends by subtracting it, exact inverse traversals of the implicit binary tree, which is why both run in O(log n).
FIG No framing: the Fenwick prefix-sum and range-query correctness under updates is real and cross-checked against naive summation in-browser. The AVAN inverse is the genuine structure — update ascends by adding the low-bit and query descends by subtracting it, exact inverse traversals of the implicit binary tree, which is why both run in O(log n).
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE EPOCH · David Lee Wise (ROOT0), with AVAN