Cartesian Tree Range Minimum
Turn range minima into lowest common ancestors while preserving duplicate-key order.
Free theory articleTurn range minima into lowest common ancestors while preserving duplicate-key order.
Concept & interpretation
The Range Minimum Query (RMQ) problem can be solved in linear time by constructing a Cartesian tree. This tree turns the array range minimum into a lowest common ancestor (LCA) problem.
Match LCA to Range Minimum
Follow these steps using the Cartesian Tree Range Minimum interactive module.
- Set Array to "Mixed" (A = [3, 1, 4, 1, 5]).
- Set Left index to "2" and Right index to "4".
- Observe the Range minimum index result, which is 3. The Range minimum value is 1.
- 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.