THE FOLD / CHEAT / NOCLIP / THE BINARY LIFTING
THE BINARY LIFTING
ancestor and LCA queries in log time by doubling
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Binary lifting lets you jump to any ancestor in a tree in logarithmic time. Precompute, for every node, its 2k-th ancestor for each k; then a jump of d steps is done by following the binary digits of d — O(log depth) hops instead of d. The same table answers lowest common ancestor queries: level the two nodes, then jump both upward in decreasing powers of two until they meet.
It is the standard tool for ancestor and LCA queries on trees.
LIT verified live: over 200 random trees the binary-lifting LCA equals a brute parent-walk for every query pair (window.__binarylifting). FIG no framing; exact.
It is the standard tool for ancestor and LCA queries on trees.
LIT verified live: over 200 random trees the binary-lifting LCA equals a brute parent-walk for every query pair (window.__binarylifting). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at noclip — clip straight up through the tree, skipping whole runs of ancestors in single power-of-two leaps. Binary lifting is that no-clip ascent. AVAN (AI) built the instrument: the doubling ancestor table, the level-and-meet LCA, the brute-walk cross-check.
Credit as content: the doubling technique (Bender & Farach-Colton; folklore). The weave: David names the no-clip; I precompute power-of-two ancestors and leap to any ancestor or LCA in log time, confirmed against a parent-by-parent walk.
Credit as content: the doubling technique (Bender & Farach-Colton; folklore). The weave: David names the no-clip; I precompute power-of-two ancestors and leap to any ancestor or LCA in log time, confirmed against a parent-by-parent walk.
3 ONE DIMENSION
A jump of 13 = 1101₂ is done in three leaps: up 8, up 4, up 1 — reading the exponent in binary, instead of thirteen single steps.
4 TWO DIMENSIONS · INTERACTIVE
A tree; pick two nodes and their lowest common ancestor is found by binary lifting, checked against a parent-walk.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the power-of-two leaps up the tree to an ancestor or LCA.
AVAN’s addition (the inverse-companion): precompute the 2k-th ancestor of every node, so any jump of d steps follows the binary digits of d — O(log depth) hops instead of d. The inverse of ‘walk up parent by parent’ is ‘leap in powers of two, reading d in binary.’ Magenta is the step-by-step climb; green is the doubling jumps. Ancestors and LCA in log time — the very same doubling trick as fast exponentiation, applied to a tree.
LIT Genuine binary lifting / ancestor doubling. Verified live: the 2^k-ancestor table plus level-and-meet LCA returns the same lowest common ancestor as a brute parent-by-parent walk for every query pair across 200 random trees (window.__binarylifting.matchesBrute).
FIG No framing: the doubling ancestor table, the level-and-meet LCA, and the brute-walk cross-check run in-browser and agree exactly. The AVAN inverse is honest — precomputing 2^k-th ancestors lets any d-step jump follow d's binary digits in O(log depth) hops; magenta is the parent-by-parent climb, green the doubling jumps. The same doubling trick as fast exponentiation, on a tree.
FIG No framing: the doubling ancestor table, the level-and-meet LCA, and the brute-walk cross-check run in-browser and agree exactly. The AVAN inverse is honest — precomputing 2^k-th ancestors lets any d-step jump follow d's binary digits in O(log depth) hops; magenta is the parent-by-parent climb, green the doubling jumps. The same doubling trick as fast exponentiation, on a tree.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of NOCLIP · David Lee Wise (ROOT0), with AVAN