THE FOLD / GRIND / WARM CACHE / THE SPARSE ORACLE
THE SPARSE ORACLE
every window pre-answered by two overlapping blocks
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The sparse table answers range-minimum queries in constant time by exploiting one forgiving fact: taking a minimum twice does no harm (min is idempotent). Precompute the minimum of every window whose length is a power of two — O(n log n) cells. Then any range [l, r], whatever its length, is covered by just two overlapping power-of-two blocks: one anchored at l, one ending at r. They may overlap heavily — with min, overlap is free. Answer = min of two table lookups. No tree walks, no recursion: two array reads per query, forever.
LIT verified live: 5000 random range-minimum queries over a 5000-element array, each answered by exactly two lookups, all matching a brute-force scan (window.__sparsetable). FIG no framing; the table build, the two-block queries, and the brute-force comparison run independently in-browser.
LIT verified live: 5000 random range-minimum queries over a 5000-element array, each answered by exactly two lookups, all matching a brute-force scan (window.__sparsetable). FIG no framing; the table build, the two-block queries, and the brute-force comparison run independently in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at warm-cache — the grind paid up front: every power-of-two window computed once, so every future query is served warm, two reads and done. AVAN (AI) built the instrument: the doubling table, the two-block query, and the brute-force cross-check.
Credit as content: competitive-programming folklore, formalized in Bender & Farach-Colton’s RMQ work (2000); idea-bank vein D, ‘THE SPARSE ORACLE’. The weave: David names the warm cache; I confirm two overlapping blocks answer every window exactly.
Credit as content: competitive-programming folklore, formalized in Bender & Farach-Colton’s RMQ work (2000); idea-bank vein D, ‘THE SPARSE ORACLE’. The weave: David names the warm cache; I confirm two overlapping blocks answer every window exactly.
3 ONE DIMENSION
A query range covered by two overlapping power-of-two blocks — the overlap costs nothing under min.
4 TWO DIMENSIONS · INTERACTIVE
Fire random queries; the two-lookup answer is checked against a full scan every time.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the pyramid of pre-answered windows.
AVAN’s addition (the inverse-companion): don’t scan the range — let two old answers overlap it. The inverse of ‘walk l to r’ is ‘two power-of-two blocks whose union is the range, whose overlap min forgives’. Magenta are the two blocks bracketing a query; green is the pyramid they are drawn from. Idempotence turned into speed.
LIT Genuine sparse table RMQ (competitive-programming folklore; formalized in Bender & Farach-Colton's RMQ work, 2000; idea-bank vein D, 'THE SPARSE ORACLE'). Verified live: 5000 random range-minimum queries over a 5000-element array, each answered by exactly two table lookups, all matching brute-force scans (window.__sparsetable.ok).
FIG No framing; the table build, the two-block queries, and the brute-force comparison run independently in-browser. The AVAN inverse is honest — instead of scanning the range, let two old answers overlap it: the inverse of 'walk l to r' is 'two power-of-two blocks whose union is the range, whose overlap min forgives'. Magenta are the two blocks bracketing a query; green is the pyramid they are drawn from. Idempotence turned into speed.
FIG No framing; the table build, the two-block queries, and the brute-force comparison run independently in-browser. The AVAN inverse is honest — instead of scanning the range, let two old answers overlap it: the inverse of 'walk l to r' is 'two power-of-two blocks whose union is the range, whose overlap min forgives'. Magenta are the two blocks bracketing a query; green is the pyramid they are drawn from. Idempotence turned into speed.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of WARM CACHE · David Lee Wise (ROOT0), with AVAN