THE FOLD / SPAWN / COLD BOOT / THE CARTESIAN TREE

THE CARTESIAN TREE

one tree, two orders — range-min and LCA are the same

1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION

A Cartesian tree is built from a sequence so it satisfies two orders at once: its in-order traversal reproduces the original array positions (a binary search tree on indices), and every parent’s value is ≤ its children’s (a min-heap on values). It is built in O(n) with a single stack.

The payoff: the lowest common ancestor of positions i and j is exactly the position of the minimum in the range a[i…j] — so range-minimum queries and LCA queries become the same problem, each convertible to the other.

LIT verified live: for random arrays, the in-order traversal equals 0,1,…,n−1, the heap property holds on values, and LCA(i,j)’s value equals the range-minimum of a[i…j] (window.__cartesiantree). FIG no framing; exact tree construction.

2 HOW IT WAS WEAVED · AI + HUMAN

David (human) seated this at cold-boot — building the whole structure from a bare array in one pass. The Cartesian tree is exactly that: one linear scan boots a tree carrying two orders. AVAN (AI) built the instrument: the O(n) stack construction, the in-order / heap checks, the LCA-equals-range-minimum test.

Credit as content: Jean Vuillemin (1980), who named the structure. The weave: David names the cold boot; I build the tree in one stack pass and show two different queries — range-minimum and lowest-common-ancestor — give the very same answer.

3 ONE DIMENSION

The array as bars by value. The Cartesian tree’s root is the global minimum; its left and right subtrees are the Cartesian trees of the segments on either side — recursively, the smallest value always rises to the top of its span.

4 TWO DIMENSIONS · INTERACTIVE

An array and its Cartesian tree. Click two positions: their lowest common ancestor lights up, and it is exactly the minimum of the range between them. Verify in-order, heap property, and LCA = range-min.

5 THREE DIMENSIONS + AVAN’S INVERSE

The green forward object: the tree floating above its array, each node the minimum of the span it covers.

AVAN’s addition (the inverse-companion): two problems that look unrelated are the same problem. ‘Minimum in a range’ is about values; ‘lowest common ancestor’ is about tree structure — yet the Cartesian tree makes each reducible to the other in linear time: range-min over a[i…j] is LCA(i,j), and LCA is a range-min over an Euler tour. The inverse of ‘a range-minimum query’ is ‘an ancestor query,’ and back again. That equivalence is why the fastest RMQ algorithm routes through LCA and the fastest LCA through RMQ. Magenta is the range on the array; green is the LCA node in the tree — one answer wearing two hats. Two questions, one structure that translates between them.

LIT Genuine Cartesian tree (Vuillemin 1980). Verified live: the O(n) stack construction yields a tree whose in-order traversal equals 0..n-1 (BST on indices), whose parent values are <= child values (min-heap), and for random ranges LCA(i,j)'s value equals min(a[i..j]) (window.__cartesiantree.inorderIsIndices && .heapProperty && .lcaIsRangeMin).

FIG No framing: the stack construction, the in-order and heap checks, and the LCA-equals-range-min test run in-browser and are exact. The AVAN inverse is honest — range-minimum (about values) and lowest-common-ancestor (about tree structure) are genuinely inter-reducible in linear time via the Cartesian tree, which is why the fastest RMQ routes through LCA and vice versa; magenta is the array range, green the LCA node.

◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of COLD BOOT · David Lee Wise (ROOT0), with AVAN