The tree a range minimum is a question about

The tree a range minimum is a question about

The Cartesian tree of 12 values: the root is the array's leftmost smallest value, and each subtree is the same construction on what lies either side of it. Every node sits at its own position along the horizontal axis and at its depth in the tree vertically, so the tree is drawn over the array rather than beside it. The minimum of any range is the lowest common ancestor of its two endpoints — for positions 2 to 8 that is position 6, holding 1. The values themselves are not needed once the tree exists: only its shape is, and a shape is far cheaper to store than a list of numbers.

Drawn at 700 × 400, wide on the page. Everything above is what cartesian-shape returns with no arguments; the caption is the generator's own, computed from the numbers in the drawing rather than written beside it.

3 essays call cartesian-shape. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about — which is what optcheck and figfill exist to catch.