THE FOLD / LOOT / THE STASH / THE FENWICK LADDER
THE FENWICK LADDER
a whole range-sum tree hidden in one array, by i & −i
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Fenwick tree (binary indexed tree). You want running totals of an array that also keeps changing. A plain prefix-sum array answers instantly but costs O(n) to update; a plain array updates instantly but costs O(n) to total. Fenwick does both in O(log n) by hiding a whole tree inside one flat array, navigated by a single bit trick: the lowest set bit,
LIT verified: after thousands of random updates, every prefix-sum and range-sum matches a naive cumulative array, each query touching only ~log₂n cells (9 for n=256). FIG ‘a ladder of binary spans’ is the picture; the
i & −i. Each cell owns a range whose width is its lowest set bit; to update you climb i += i&−i, to total you descend i −= i&−i.LIT verified: after thousands of random updates, every prefix-sum and range-sum matches a naive cumulative array, each query touching only ~log₂n cells (9 for n=256). FIG ‘a ladder of binary spans’ is the picture; the
i&−i navigation is exact.2 HOW IT WAS WEAVED · AI + HUMAN
David (human) brought the thread — the corpus is full of bit-level machinery (the ISA/kernel work, the byte atoms) and running ledgers, and the idea that a clever index encodes a whole structure. AVAN (AI) built this instrument: the tree, the climb/descend animation, and the 3D span ladder.
The weave: David names the hidden ladder and its seat at THE STASH (running totals of the hoard); I make each cell’s binary span a strip in 1D, the update/query live in 2D, and the ladder turning in 3D. The sphere is the seam.
The weave: David names the hidden ladder and its seat at THE STASH (running totals of the hoard); I make each cell’s binary span a strip in 1D, the update/query live in 2D, and the ladder turning in 3D. The sphere is the seam.
3 ONE DIMENSION
Each index’s responsibility: cell i owns the range of width i & −i ending at i (its lowest set bit). Odd cells own width 1, cell 8 owns 8, cell 16 owns 16 — a nested staircase of power-of-two spans hiding in one array.
4 TWO DIMENSIONS · INTERACTIVE
Live. Click a value cell to add 1 — watch the climb
i += i&−i light the ~log n tree cells it updates. Slide the prefix to total 1…k — watch the descend i −= i&−i, always matching the naive sum.prefix k = 8
5 THREE DIMENSIONS + AVAN’S INVERSE
The ladder in space: each cell sits at a height equal to its lowest-set-bit level, its bar spanning the range it owns. Green is an update climb from a cell — hop up by adding the low bit,
i += i&−i, until you leave the array.AVAN’s addition (the inverse-companion): the magenta path is a query descend — hop down by subtracting the low bit,
i −= i&−i, gathering the cells that sum a prefix. Update and query are exact inverses: the same low bit, added to build the total or stripped to read it. One ladder climbed both ways.LIT A genuine Fenwick tree. Verified live: after 5000 random updates every prefix-sum and range-sum matches a naive cumulative array, each query touching only ~log₂n cells (max 7 for n=64). The i&−i responsibility spans, the update climb (i+=i&−i), and the query descend (i−=i&−i) are the exact navigation (verifiable: window.__fenwick.matchesNaive===true).
FIG 'A ladder of binary spans' is the picture; the bit navigation and the O(log n) cost are exact. The whole balanced structure really does live inside one array with no pointers — the arithmetic of the lowest set bit is the tree.
FIG 'A ladder of binary spans' is the picture; the bit navigation and the O(log n) cost are exact. The whole balanced structure really does live inside one array with no pointers — the arithmetic of the lowest set bit is the tree.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE STASH · David Lee Wise (ROOT0), with AVAN