Cartesian Tree Range Minimum

Min-Cartesian Tree Properties

A min-Cartesian tree built from an array satisfies two properties: it is a min-heap (parents are smaller than their children), and an in-order traversal yields the original array elements in their original order. Ties are broken by taking the leftmost minimum. We build it in linear time using a monotonic stack.

Worked example: Mixed array

Consider the array [3, 1, 4, 1, 5] and a query for the range [2, 4].

1. The array indices are 0 to 4. We build the Cartesian tree using a stack. The minimum value is 1 at index 1 (leftmost tie-breaker), which becomes the root.
2. For the query endpoints [2, 4], the actual valid subarray indices are from left=2 to right=4. The elements are A[2]=4, A[3]=1, A[4]=5.
3. The range minimum over indices [2, 4] is 1, which occurs at index 3.
4. In the Cartesian tree, the Lowest Common Ancestor (LCA) of nodes 2 and 4 is node 3. Thus, LCA(2, 4) gives the index of the range minimum.

Match LCA to Range Minimum

Follow these steps using the Cartesian Tree Range Minimum interactive module.

1. Set Array to "Mixed" (A = [3, 1, 4, 1, 5]).
2. Set Left index to "2" and Right index to "4".
3. Observe the Range minimum index result, which is 3. The Range minimum value is 1.
4. Change the Array to "Decreasing". The array is now [5, 4, 3, 2, 1]. Notice how the tree becomes a single line going right, and the root is node 4.

Limitations

This visualization builds the exact Cartesian tree structure and computes LCA path-by-path, which demonstrates the mathematical correspondence. In highly optimized RMQ implementations (such as Fischer-Heun), the full tree is not materialized with objects; instead, bitwise operations on Euler tours and block minimums are used. Additionally, this module clamps queries to the valid array bounds [0, n-1] rather than rejecting out-of-bounds queries.

References

For more details on reducing RMQ to LCA and constructing Cartesian trees in linear time, see: https://cp-algorithms.com/graph/rmq_linear.html