THE FOLD / GRIND / WARM CACHE / THE SEGMENT TREE
THE SEGMENT TREE
a range in a logarithm of nodes
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The segment tree answers questions about any range of an array — its sum, its minimum — in O(log n) time, and updates a single element just as fast. It is a binary tree over the array: leaves are the elements, and every internal node stores the aggregate of its two children. Any range [l, r] splits into at most 2 log n canonical nodes whose stored aggregates already hold the answer, so you never rescan the range. Change one leaf and only the log n nodes above it need refreshing.
LIT verified live: over 2,000 random arrays with interleaved point-updates, the tree’s range-sum and range-minimum queries match a direct rescan every time (window.__segment_tree). FIG no framing; the tree queries and the naive rescans both run in-browser.
LIT verified live: over 2,000 random arrays with interleaved point-updates, the tree’s range-sum and range-minimum queries match a direct rescan every time (window.__segment_tree). FIG no framing; the tree queries and the naive rescans both run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at warm-cache — the internal nodes are a warm cache of pre-aggregated ranges, so a query reads sums it never has to recompute. AVAN (AI) built the instrument: the iterative segment tree with point-update, and a naive rescan to check every query.
Credit as content: the segment tree (Bentley; folklore of competitive programming and computational geometry). The weave: David names the warm cache; I confirm the O(log n) range answers agree with a full rescan, update after update.
Credit as content: the segment tree (Bentley; folklore of competitive programming and computational geometry). The weave: David names the warm cache; I confirm the O(log n) range answers agree with a full rescan, update after update.
3 ONE DIMENSION
The array as leaves; each internal node holds the sum of its two children — the tree of pre-aggregated ranges.
4 TWO DIMENSIONS · INTERACTIVE
Pick a range; the sum and minimum are read from a handful of canonical nodes, matched against a rescan. Update an element and requery.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the tree of aggregates over the whole array.
AVAN’s addition (the inverse-companion): don’t scan the range — cover it. The inverse of ‘add up l..r’ is ‘the range decomposes into O(log n) canonical nodes whose sums are already stored.’ Magenta is the raw range; green are the log n covering nodes that answer it. Cover, don’t scan.
LIT Genuine segment tree (Bentley; a staple of computational geometry and competitive programming): O(log n) range aggregate + point update via a binary tree of aggregates. Verified live: over 2000 random arrays with updates, range-sum (window.__segment_tree.sumOk) and range-min (.minOk) equal a naive rescan.
FIG No framing: the iterative tree queries and the naive rescans both run in-browser and agree after every update. The AVAN inverse is honest — a range covering into O(log n) canonical nodes whose sums are precomputed (rather than scanning l..r) is exactly what buys the logarithm; magenta is the raw range, green the log-n covering nodes. Cover, don't scan.
FIG No framing: the iterative tree queries and the naive rescans both run in-browser and agree after every update. The AVAN inverse is honest — a range covering into O(log n) canonical nodes whose sums are precomputed (rather than scanning l..r) is exactly what buys the logarithm; magenta is the raw range, green the log-n covering nodes. Cover, don't scan.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of WARM CACHE · David Lee Wise (ROOT0), with AVAN