THE FOLD / SPAWN / GENESIS BLOCK / THE EULER TOUR
THE EULER TOUR
flatten a tree so every subtree is a contiguous range
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Euler tour technique flattens a tree into a flat array by a depth-first walk that records each node’s entry time (tin) and exit time (tout). The magic: the subtree of any node v is exactly the contiguous range [tin[v], tout[v]] in the array.
So ‘sum over a subtree,’ ‘is u a descendant of v,’ and ‘subtree size’ all become O(1)–O(log n) range queries on an array — letting you point segment trees and Fenwick trees at tree problems they were never built for.
LIT verified live: for 200 random trees, the subtree of every node v equals exactly the set of nodes whose entry time lies in [tin[v], tout[v]], and its size equals tout[v] − tin[v] + 1 (window.__eulertour). FIG no framing; exact tree flattening.
So ‘sum over a subtree,’ ‘is u a descendant of v,’ and ‘subtree size’ all become O(1)–O(log n) range queries on an array — letting you point segment trees and Fenwick trees at tree problems they were never built for.
LIT verified live: for 200 random trees, the subtree of every node v equals exactly the set of nodes whose entry time lies in [tin[v], tout[v]], and its size equals tout[v] − tin[v] + 1 (window.__eulertour). FIG no framing; exact tree flattening.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at genesis-block — the tree unrolled from its single root, the first structure laid down in order. The Euler tour is that unrolling: a hierarchy serialised into one line. AVAN (AI) built the instrument: the DFS entry/exit timestamps, the subtree-equals-range check, the interactive flattening.
Credit as content: the Euler tour technique, standard in algorithm design and rooted in Tarjan–Vishkin parallel tree algorithms (1985). The weave: David names the genesis block; I timestamp a depth-first walk and prove every subtree is a contiguous slice of the resulting array.
Credit as content: the Euler tour technique, standard in algorithm design and rooted in Tarjan–Vishkin parallel tree algorithms (1985). The weave: David names the genesis block; I timestamp a depth-first walk and prove every subtree is a contiguous slice of the resulting array.
3 ONE DIMENSION
A depth-first walk assigning entry (tin) and exit (tout) times. Enter a node, recurse into its children, then leave — so a whole subtree occupies one unbroken span of times.
4 TWO DIMENSIONS · INTERACTIVE
A random tree and its flattened array. Click a node: its subtree lights up in the tree, and the contiguous range [tin, tout] lights up identically in the array. Verify subtree == range and size == tout − tin + 1.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the tree beside its flattened array, each subtree a contiguous block.
AVAN’s addition (the inverse-companion): a branching, two-dimensional hierarchy becomes a one-dimensional nesting of intervals. Parent–child in the tree turns into range containment on the line — [tin[v], tout[v]] contains [tin[u], tout[u]] iff u lies in v’s subtree — so tree ancestry is interval nesting, exactly. The inverse of ‘a branching hierarchy’ is ‘a set of nested intervals on a line.’ That is precisely why flat array structures — Fenwick trees, segment trees — can answer questions about a tree: the tree was an interval order all along. Magenta is the tree’s edges; green is the nested intervals encoding the same ancestry. Hierarchy is containment in disguise.
LIT Genuine Euler tour technique (standard; rooted in Tarjan-Vishkin parallel tree algorithms 1985). Verified live: for 200 random trees, the subtree of every node v equals exactly {u : tin[v] <= tin[u] <= tout[v]} and has size tout[v]-tin[v]+1 (window.__eulertour.subtreeIsRange).
FIG No framing: the DFS entry/exit timestamps and the subtree-equals-range check run in-browser and are exact. The AVAN inverse is honest — parent-child in the tree becomes interval containment on the line ([tin_v,tout_v] contains [tin_u,tout_u] iff u is in v's subtree), so tree ancestry is exactly interval nesting, which is why flat array structures can answer tree queries; magenta is the tree edges, green the nested intervals.
FIG No framing: the DFS entry/exit timestamps and the subtree-equals-range check run in-browser and are exact. The AVAN inverse is honest — parent-child in the tree becomes interval containment on the line ([tin_v,tout_v] contains [tin_u,tout_u] iff u is in v's subtree), so tree ancestry is exactly interval nesting, which is why flat array structures can answer tree queries; magenta is the tree edges, green the nested intervals.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of GENESIS BLOCK · David Lee Wise (ROOT0), with AVAN