THE FOLD / CO-OP / SHARED MEMORY / THE SPARSE TABLE
THE SPARSE TABLE
O(1) range-min from two overlapping precomputed blocks
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The sparse table answers range-minimum queries in O(1) after O(n log n) preprocessing. It stores the minimum of every power-of-two block; then any range [l,r] is covered by just two overlapping blocks — and the overlap is harmless because min is idempotent (min(x,x)=x), so double-counting the overlap changes nothing.
It is the classic static range-min / range-max structure.
LIT verified live: over 200 random arrays the sparse-table range-minimum equals a brute scan for every query (window.__sparsetable). FIG no framing; exact.
It is the classic static range-min / range-max structure.
LIT verified live: over 200 random arrays the sparse-table range-minimum equals a brute scan for every query (window.__sparsetable). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at shared-memory — the precomputed answers held in a shared table, so any query reads two cells and is done. The sparse table is that shared lookup. AVAN (AI) built the instrument: the doubling block-minimum table, the two-block O(1) query, the brute cross-check.
Credit as content: the sparse table for RMQ (Bender & Farach-Colton). The weave: David names the shared memory; I precompute every power-of-two block’s minimum and answer any range with two overlapping lookups, confirmed against a direct scan.
Credit as content: the sparse table for RMQ (Bender & Farach-Colton). The weave: David names the shared memory; I precompute every power-of-two block’s minimum and answer any range with two overlapping lookups, confirmed against a direct scan.
3 ONE DIMENSION
A range of length L is covered by two blocks of size 2⌊log₂L⌋ — one anchored at the left, one at the right. They overlap in the middle, but for min that overlap costs nothing.
4 TWO DIMENSIONS · INTERACTIVE
An array; pick a range and the sparse table returns its minimum from two overlapping blocks, checked against a scan.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the two overlapping blocks that answer any range in O(1).
AVAN’s addition (the inverse-companion): precompute the minimum of every power-of-two block, then any range is the min of just two overlapping blocks — and overlap is fine because min is idempotent (min(x,x)=x), so double-counting doesn’t matter. The inverse of ‘scan the whole range’ is ‘cover it with two overlapping precomputed blocks.’ Magenta is the linear scan; green is the two O(1) block lookups. Idempotence is what lets the blocks overlap freely — it fails for sum, which is why sum needs a different structure.
LIT Genuine sparse table for RMQ (Bender & Farach-Colton). Verified live: the doubling block-minimum table answers any range with two overlapping blocks and equals a brute range-minimum scan for every query across 200 random arrays (window.__sparsetable.matchesBrute).
FIG No framing: the doubling block-minimum table, the two-block O(1) query, and the brute cross-check run in-browser and agree exactly. The AVAN inverse is honest — precomputing power-of-two block minima lets any range be the min of two overlapping blocks, and overlap costs nothing because min is idempotent; magenta is the linear scan, green the two O(1) lookups. Idempotence is why the blocks can overlap (sum, not idempotent, needs another structure).
FIG No framing: the doubling block-minimum table, the two-block O(1) query, and the brute cross-check run in-browser and agree exactly. The AVAN inverse is honest — precomputing power-of-two block minima lets any range be the min of two overlapping blocks, and overlap costs nothing because min is idempotent; magenta is the linear scan, green the two O(1) lookups. Idempotence is why the blocks can overlap (sum, not idempotent, needs another structure).
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of SHARED MEMORY · David Lee Wise (ROOT0), with AVAN