THE FOLD / GRIND / THE-MAINFRAME / THE HEAVY-LIGHT DECOMPOSITION
THE HEAVY-LIGHT DECOMPOSITION
a tree cut into heavy chains
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Heavy-light decomposition cuts a tree into a few long chains so that any root-to-node path crosses only O(log n) of them. At each node, the edge to its heavy child — the child with the largest subtree — is kept; all other edges are “light.” Following heavy edges links nodes into vertical chains, and the key fact is that any path from the root descends through at most log₂ n light edges (each light step at least halves the remaining subtree). Lay each chain in a segment tree or Fenwick array, and a path query — sum, max, update along the route between two nodes — becomes O(log² n) instead of O(n).
LIT verified live: over 3000 random trees, the path-sum between two nodes computed by climbing heavy chains equals a brute-force walk of the actual path (window.__heavy_light). FIG no framing; the heavy-child decomposition and the chain-climbing query run in-browser.
LIT verified live: over 3000 random trees, the path-sum between two nodes computed by climbing heavy chains equals a brute-force walk of the actual path (window.__heavy_light). FIG no framing; the heavy-child decomposition and the chain-climbing query run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-mainframe — the tree pre-cut into heavy chains so path queries run in log-squared time on contiguous arrays. AVAN (AI) built the instrument: the subtree sizes, the heavy-child chains, the chain-climbing path query, and the brute-force cross-check.
Credit as content: heavy-light decomposition (Sleator & Tarjan lineage; standard competitive/algorithmic technique). The weave: David names the mainframe; I confirm the chain-climbing path sum equals the true path sum.
Credit as content: heavy-light decomposition (Sleator & Tarjan lineage; standard competitive/algorithmic technique). The weave: David names the mainframe; I confirm the chain-climbing path sum equals the true path sum.
3 ONE DIMENSION
Each node keeps the edge to its heaviest child; following heavy edges makes vertical chains a path crosses few of.
4 TWO DIMENSIONS · INTERACTIVE
Pick two nodes; the path-sum climbs O(log n) chains and matches a brute-force walk of the whole path.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the path answer, from a few chain segments.
AVAN’s addition (the inverse-companion): don’t walk the path node by node — jump chains. The inverse of ‘traverse the O(n) path’ is ‘heavy chains lay the tree flat; a path touches only O(log n) chain segments.’ Magenta is the node-by-node walk; green is the chain segments that cover it. Chains flatten the tree.
LIT Genuine heavy-light decomposition (Sleator & Tarjan lineage; standard algorithmic technique). Verified live: over 3000 random trees, the path-sum between two nodes computed by climbing heavy chains (O(log n) chain segments) equals a brute-force walk of the true tree path (window.__heavy_light.matchesBrute).
FIG No framing: the heavy-child decomposition and the chain-climbing query run in-browser. The AVAN inverse is honest — instead of walking the O(n) path node by node, heavy chains lay the tree flat so a path touches only O(log n) contiguous chain segments. Magenta is the node-by-node walk; green is the chain segments that cover it. Chains flatten the tree.
FIG No framing: the heavy-child decomposition and the chain-climbing query run in-browser. The AVAN inverse is honest — instead of walking the O(n) path node by node, heavy chains lay the tree flat so a path touches only O(log n) contiguous chain segments. Magenta is the node-by-node walk; green is the chain segments that cover it. Chains flatten the tree.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE-MAINFRAME · David Lee Wise (ROOT0), with AVAN