Cartesian Trees: Linear-Time Monotonic Stack Construction & RMQ-LCA Duality

1. Linear-Time $\Theta(N)$ Right-Spine Construction via Monotonic Stack

Suppose we have already built the Cartesian tree for prefix $A[0..i-1]$. Because index $i$ is larger than every index in ${0, \dots, i-1}$, node $i$ must be placed somewhere along the rightmost spine of the current tree (and cannot have a right child yet). As we climb up the right spine from the bottommost node, any spine node $s$ with $A[s] > A[i]$ violates the min-heap invariant if $s$ remains above $i$. Therefore:

1. Pop all nodes $s$ from the right-spine stack that have $A[s] > A[i]$; let $last$ be the last node popped (the shallowest popped node with $A[last] > A[i]$).
2. Make $last$ the left child of $i$ (left[i] = last), preserving the inorder requirement because all indices in $last$'s subtree are $< i$.
3. If the stack is still non-empty, its top node $p$ satisfies $A[p] \le A[i]$; attach $i$ as the right child of $p$ (right[p] = i). Push $i$ onto the right-spine stack.

Because each index $i \in [0, N-1]$ is pushed onto the right-spine stack once and popped at most once, the entire construction runs in at most $2N$ stack operations—exact $\Theta(N)$ time!

2. Production Implementation: $\Theta(N)$ Cartesian Tree & All-Subarray-Minimums Summation

/**
 * Constructs the Min-Cartesian Tree of arr[0..N-1] in exact Theta(N) time
 * using a monotonic right-spine stack.
 * Ties broken by smaller index (arr[stack[top]] > arr[i] pops strictly greater values).
 */
function buildCartesianTree(arr) {
  const n = arr.length;
  const parent = new Int32Array(n).fill(-1);
  const left = new Int32Array(n).fill(-1);
  const right = new Int32Array(n).fill(-1);
  const stack = new Int32Array(n);
  let top = -1;

  for (let i = 0; i < n; i++) {
    let lastPopped = -1;
    // Pop nodes from right spine that are strictly greater than arr[i]
    while (top >= 0 && arr[stack[top]] > arr[i]) {
      lastPopped = stack[top--];
    }
    // The shallowest popped node becomes the left child of i
    if (lastPopped !== -1) {
      left[i] = lastPopped;
      parent[lastPopped] = i;
    }
    // If stack is non-empty, i becomes the right child of stack[top]
    if (top >= 0) {
      right[stack[top]] = i;
      parent[i] = stack[top];
    }
    stack[++top] = i;
  }

  // The root of the entire Cartesian tree is at the bottom of the right spine (stack[0])
  const root = n > 0 ? stack[0] : -1;
  return { root, parent, left, right };
}

/**
 * Application: Sum of min(A[L..R]) over all N*(N+1)/2 subarrays in O(N) time!
 * In the Cartesian tree, node i is the minimum for all subarrays [L, R]
 * where L is in i's left subtree (+ i) and R is in i's right subtree (+ i).
 */
function sumOfSubarrayMinimums(arr) {
  const n = arr.length;
  const { root, left, right } = buildCartesianTree(arr);
  const sz = new Int32Array(n);
  let totalSum = 0;

  // Iterative post-order traversal
  const order = [];
  const stack = root !== -1 ? [root] : [];
  while (stack.length > 0) {
    const u = stack.pop();
    order.push(u);
    if (left[u] !== -1) stack.push(left[u]);
    if (right[u] !== -1) stack.push(right[u]);
  }

  for (let idx = order.length - 1; idx >= 0; idx--) {
    const u = order[idx];
    const szL = left[u] !== -1 ? sz[left[u]] : 0;
    const szR = right[u] !== -1 ? sz[right[u]] : 0;
    sz[u] = 1 + szL + szR;
    totalSum += arr[u] * (szL + 1) * (szR + 1);
  }
  return totalSum;
}

3. Complexity Matrix