The Range Minimum Hides a Tree

A range-minimum query sounds like an array problem:

given A[0..n-1], return the index of the smallest value in A[i..j]

The surprising answer is that the array is carrying a tree.

A Cartesian tree over an array has two contracts:

inorder traversal visits indices 0, 1, 2, ..., n-1
each parent has value <= each child

The first contract preserves array order. The second contract makes small values rise toward the root. Together they imply the useful fact:

RMQ(i, j) = LCA(i, j) in the Cartesian tree

That is a reduction, not just a drawing. It says a contiguous subarray question can be turned into a tree ancestor question.

The Splitter

Assume for a moment all values are distinct. Take a query interval A[i..j]. Let k be the index of the minimum value inside that interval.

In the Cartesian tree, k must sit above every other index in i..j. If some smaller ancestor inside the interval existed, k would not be the minimum. If k were below a node inside the interval, the heap property would put that node no larger than A[k], again contradicting the choice of k.

The other half is the inorder contract. Any node whose index lies between i and j appears between them in the inorder traversal. The first node that can separate index i from index j while still being inside that interval is their lowest common ancestor. Because the tree is heap-ordered by array value, that splitter is exactly the minimum.

With duplicate values, the tree needs a tie rule. The lab below lets you choose leftmost or rightmost duplicate minima. The theorem still holds as long as the same tie rule is used by the stack construction, the heap comparison, and the RMQ answer.

Build It With a Stack

The direct recursive definition is clear but wasteful:

root = index of minimum A[l..r]
left subtree = Cartesian tree of A[l..root-1]
right subtree = Cartesian tree of A[root+1..r]

If we scan for a minimum at every recursive call, a sorted array costs quadratic time. The linear construction uses a monotone stack:

for each index i from left to right:
    last = none
    while stack top is larger than A[i]:
        last = pop stack
    if stack is nonempty:
        i becomes the right child of the stack top
    if last exists:
        last becomes the left child of i
    push i

Every index is pushed once. Every index can be popped once. The stack is not a heuristic; it is the right spine of the partial Cartesian tree.

Jean Vuillemin’s 1980 paper introduced Cartesian trees as a geometric data structure whose labels form both a binary-search order in one coordinate and a heap-like tournament in the other.¹ Gabow, Bentley, and Tarjan used Cartesian trees in the range-minimum-query lineage a few years later.² The RMQ/LCA connection then became a standard bridge in work on succinct and constant-time query structures. Bender and Farach-Colton’s LCA paper states the link directly: the RMQ of two array indices is the LCA of the corresponding nodes in the Cartesian tree.³

The lab here stops before the full constant-time preprocessing machinery. It builds the tree in linear time, answers the displayed LCA by climbing parent chains, and exhaustively audits every interval in the small example. The point is to make the structural reduction visible.

Lab: The Minimum Becomes an Ancestor

Array jagged telemetry duplicate minima wide valley sawtooth Duplicate tie leftmost minimum rightmost minimum Query start

2

Query end

9

This is a structural RMQ/LCA lab, not a full constant-time RMQ implementation. The displayed LCA is found by parent climbing because the examples are intentionally small.

What The Audit Proves

The exported Node audit reports 43 named checks: five invariants for each of the eight array/tie-policy cases, plus three duplicate and single-point edge checks. For each main case it checks:

inorder traversal is exactly 0,1,2,...,n-1
the heap property holds under the selected tie rule
there is exactly one root
the displayed RMQ equals the displayed LCA
every interval in the array has RMQ(i,j) = LCA(i,j)

Representative outputs from the current script:

jagged telemetry, leftmost, query 2..9:
  RMQ index 6, LCA index 6, value 28
  tree height 5, stack pops 10, max stack 3

duplicate minima, query 4..8:
  leftmost tie  -> RMQ index 4
  rightmost tie -> RMQ index 8

sawtooth, query 0..11:
  RMQ index 11, LCA index 11, value 0

The compact reproduction check is:

const lab = require("./assets/js/cartesian-rmq-lab.js");
const EXPECTED_SCENARIOS = 4;
const EXPECTED_TIES = 2;
const EXPECTED_MAIN_CASES = 8;
const EXPECTED_EDGE_CASES = 3;
const EXPECTED_ROWS = 11;
const EXPECTED_CHECKS = 43;
const EXPECTED_INTERVALS = 78;
const EXPECTED_INTERVAL_COUNTS = [EXPECTED_INTERVALS];
const EXPECTED_CASE_SHAPE = [
  "jagged/left:5:78",
  "jagged/right:5:78",
  "plateau/left:5:78",
  "plateau/right:5:78",
  "saw/left:5:78",
  "saw/right:5:78",
  "valley/left:5:78",
  "valley/right:5:78"
];
const EXPECTED_EDGE_SHAPE = [
  "plateau left tie:1:4",
  "plateau right tie:1:8",
  "single point:1:5"
];
const EXPECTED_TOTALS = {
  scenarios: EXPECTED_SCENARIOS,
  ties: EXPECTED_TIES,
  mainCases: EXPECTED_MAIN_CASES,
  edgeCases: EXPECTED_EDGE_CASES,
  passed: EXPECTED_ROWS,
  total: EXPECTED_ROWS,
  passedChecks: EXPECTED_CHECKS,
  totalChecks: EXPECTED_CHECKS
};

function sameJson(left, right) {
  return JSON.stringify(left) === JSON.stringify(right);
}

const audit = lab.auditCartesianRmqLab();
const auditShape = {
  totals: {
    scenarios: audit.scenarios,
    ties: new Set(audit.cases.map((row) => row.tie)).size,
    mainCases: audit.cases.length,
    edgeCases: audit.edgeCases.length,
    passed: audit.passed,
    total: audit.total,
    passedChecks: audit.passedChecks,
    totalChecks: audit.totalChecks
  },
  caseChecks: audit.cases
    .map((row) => `${row.scenario}/${row.tie}:${row.totalChecks}:${row.intervalsChecked}`)
    .sort(),
  edgeChecks: audit.edgeCases
    .map((row) => `${row.name}:${row.totalChecks}:${row.rmqIndex}`)
    .sort(),
  intervalCounts: Array.from(new Set(audit.cases.map((row) => row.intervalsChecked)))
    .sort((a, b) => a - b)
};
const shapeErrors = [
  sameJson(auditShape.totals, EXPECTED_TOTALS) ? null : "totals",
  sameJson(auditShape.intervalCounts, EXPECTED_INTERVAL_COUNTS) ? null : "intervalCounts",
  sameJson(auditShape.caseChecks, EXPECTED_CASE_SHAPE) ? null : "caseChecks",
  sameJson(auditShape.edgeChecks, EXPECTED_EDGE_SHAPE) ? null : "edgeChecks"
].filter(Boolean);
if (shapeErrors.length) {
  throw new Error(
    `audit shape drifted in ${shapeErrors.join(", ")}:\n` +
    JSON.stringify(auditShape, null, 2)
  );
}
const summary =
  `${audit.passed}/${audit.total} audit rows and ` +
  `${audit.passedChecks}/${audit.totalChecks} checks passed`;
const failedCases = audit.details.filter(
  (row) => !row.passed || row.passedChecks !== row.totalChecks
);
if (failedCases.length || !audit.ok ||
    audit.passed !== audit.total ||
    audit.passedChecks !== audit.totalChecks) {
  throw new Error(JSON.stringify({
    summary,
    errors: audit.errors,
    failedCases,
    shapeErrors,
    auditShape
  }, null, 2));
}

console.table(audit.cases.map((row) => ({
  scenario: row.scenario,
  tie: row.tie,
  intervals: row.intervalsChecked,
  rmq: row.minIndex,
  lca: row.lcaIndex,
  value: row.value,
  height: row.height,
  pops: row.pops,
  checks: `${row.passedChecks}/${row.totalChecks}`
})));
console.table(audit.edgeCases.map((row) => ({
  edge: row.name,
  rmqIndex: row.rmqIndex,
  checks: `${row.passedChecks}/${row.totalChecks}`
})));
console.log(summary);

The duplicate-minimum case is the useful edge. The array contains several 2 values. Neither answer is inherently wrong. The structure must declare which equal value wins, then keep that policy consistent everywhere.

Why This Reduction Matters

Static RMQ has many possible implementations:

scan the interval each time:     O(1) preprocessing, O(width) query
sparse table:                    O(n log n) preprocessing, O(1) query
Cartesian tree plus LCA:         reduce RMQ to a tree problem
succinct RMQ structures:         exploit the tree shape near information limits

The Cartesian tree route is beautiful because it separates two ideas that are easy to confuse:

1. The array-specific part is just the tree construction.
2. The query-speed part can be delegated to an LCA data structure.

Bender and Farach-Colton used an Euler tour to reduce LCA back to an RMQ over tree depths, then used the plus-minus-one structure of that depth array to get a simple optimal algorithm.³ That circular-looking pair of reductions is not a paradox. It says RMQ and LCA share a core shape, and the implementation wins by choosing the representation where that shape is easiest to preprocess.

Where The Stack Gets Its Power

The monotone stack works because only the right spine of the partial tree is still negotiable.

After scanning A[0..i-1], all earlier nodes have fixed inorder positions. The new node i must be to the right of everything already seen. It can only become a right child somewhere on the right spine, or it can steal a suffix of that spine as its left subtree. Popping larger spine nodes finds exactly that suffix.

That is the same shape as many monotone-stack algorithms:

nearest smaller element
largest rectangle in a histogram
stock-span style waits
Cartesian tree construction

The stack is a certificate that the algorithm did not rescan old work. Every element leaves the stack once, at the moment a smaller later value proves where that element belongs.

The Card To Keep

For an array that never changes:

build the Cartesian tree once
preprocess for LCA if query volume justifies it
answer interval minima through ancestor structure

For an array that changes, this exact structure is no longer the whole answer. One update can change many ancestor relationships. Then a segment tree, Fenwick tree for prefix-like operations, block decomposition, or a dynamic tree becomes the better starting point.

The Cartesian tree earns its place when the data is static and the query is local in array order but extremal in value. It turns a flat interval into the first ancestor where the two ends meet.

1. Jean Vuillemin, “A Unifying Look at Data Structures”, Communications of the ACM, 23(4), 1980. A public PDF copy is hosted in Princeton course materials: geo-st.pdf. ↩

2. Harold N. Gabow, Jon Louis Bentley, and Robert E. Tarjan, “Scaling and related techniques for geometry problems”, Proceedings of the 16th Annual ACM Symposium on Theory of Computing, 1984. The paper is a classic source in the Cartesian-tree/RMQ lineage. ↩

3. Michael A. Bender and Martin Farach-Colton, “The LCA Problem Revisited”, LATIN 2000. The paper states the RMQ and LCA problems together and gives the Cartesian-tree reduction RMQ_A(i,j) = LCA_C(i,j). ↩ ↩²