THE FOLD / GRIND / THE-CRON-JOB / THE SQRT DECOMPOSITION
THE SQRT DECOMPOSITION
√n blocks answer range sums
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Square-root decomposition is the simplest way to answer range queries fast. Split an array of n elements into blocks of size about √n and precompute a summary (here, a sum) for each block. To sum any range, add the few loose elements at the two ends one by one, and for the whole blocks in between just add their precomputed sums — so any query touches at most about 2√n items instead of n. A point update fixes one element and its block’s summary in O(1). It is the humble ancestor of segment trees and Fenwick trees — less powerful, but astonishingly easy and general (it works for any associative summary).
LIT verified live: over 3000 arrays and 30 mixed operations each, block range-sums with point updates exactly equal a brute-force recomputation (window.__sqrt_decomposition). FIG no framing; the block summaries and a brute-force sum run in-browser.
LIT verified live: over 3000 arrays and 30 mixed operations each, block range-sums with point updates exactly equal a brute-force recomputation (window.__sqrt_decomposition). FIG no framing; the block summaries and a brute-force sum run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-cron-job — the array carved into regular blocks, each keeping a running summary the query hops across. AVAN (AI) built the instrument: the √n blocking, the partial-plus-whole-block query, the point update, and the brute-force check.
Credit as content: square-root decomposition is classic algorithmic folklore. The weave: David names the cron job; I confirm the block sums answer every range query exactly, in O(√n).
Credit as content: square-root decomposition is classic algorithmic folklore. The weave: David names the cron job; I confirm the block sums answer every range query exactly, in O(√n).
3 ONE DIMENSION
The array split into √n blocks, each with a sum; a range adds loose ends element-by-element and whole blocks in one hop.
4 TWO DIMENSIONS · INTERACTIVE
Pick a range; the sum uses partial ends plus whole-block sums, matching a brute-force total.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the range sum, in O(√n) steps.
AVAN’s addition (the inverse-companion): don’t add every element — hop the blocks. The inverse of ‘scan the range, O(n)’ is ‘precompute √n block sums; a range is a few loose ends plus whole-block jumps, O(√n).’ Magenta is the element-by-element scan; green is the block hops. Summaries turn a scan into jumps.
LIT Genuine square-root decomposition (classic algorithmic folklore; ancestor of segment/Fenwick trees). Verified live: over 3000 random arrays × 30 mixed operations, √n-block range-sums (loose ends elementwise + whole blocks by summary) with O(1) point updates exactly equal a brute-force recomputation (window.__sqrt_decomposition.matchesBrute).
FIG No framing: the block summaries and a brute-force sum run in-browser. The AVAN inverse is honest — instead of scanning the whole range (O(n)), precomputed √n block sums turn a range into a few loose ends plus whole-block jumps, O(√n). Magenta is the element-by-element scan; green is the block hops. Summaries turn a scan into jumps.
FIG No framing: the block summaries and a brute-force sum run in-browser. The AVAN inverse is honest — instead of scanning the whole range (O(n)), precomputed √n block sums turn a range into a few loose ends plus whole-block jumps, O(√n). Magenta is the element-by-element scan; green is the block hops. Summaries turn a scan into jumps.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE-CRON-JOB · David Lee Wise (ROOT0), with AVAN