Range Minimum Query

Given a static array, answer $\min a[l..r]$ for many $(l,r)$.

The methods

Method	Preprocess	Query	Space	Note
Naive	$O(1)$	$O(n)$	$O(1)$	fine for few queries
Precompute all	$O(n^2)$	$O(1)$	$O(n^2)$	$n\le 2000$
Sparse table	$O(n\log n)$	$O(1)$	$O(n\log n)$	the default
Segment tree	$O(n)$	$O(\log n)$	$O(n)$	supports updates
Sqrt decomposition	$O(n)$	$O(\sqrt{n})$	$O(n)$	supports weird ops
Farach-Colton-Bender	$O(n)$	$O(1)$	$O(n)$	optimal, big constant
Block + sparse table hybrid	$O(n)$	$O(1)$	$O(n)$	the practical $O(n)$ version

Write the sparse table. Fifteen lines, $O(1)$ queries, tiny constant.

int sp[LOG][MAXN], lg[MAXN];
void build(const vector<int>& a) {
    int n = a.size();
    for (int i = 2; i <= n; i++) lg[i] = lg[i/2] + 1;
    for (int i = 0; i < n; i++) sp[0][i] = a[i];
    for (int k = 1; (1 << k) <= n; k++)
        for (int i = 0; i + (1 << k) <= n; i++)
            sp[k][i] = min(sp[k-1][i], sp[k-1][i + (1 << (k-1))]);
}
int query(int l, int r) {                     // inclusive
    int k = lg[r - l + 1];
    return min(sp[k][l], sp[k][r - (1 << k) + 1]);
}

The two blocks overlap, which is fine because min is idempotent. For non-idempotent operations use a disjoint sparse table.

The RMQ ↔ LCA equivalence

The two problems are interchangeable, and both directions are used:

LCA → RMQ. Take an Euler tour recording depths; $\mathrm{LCA}(u,v)$ is the minimum-depth entry between their first occurrences. Consecutive depths differ by $\pm 1$, which is the ±1 RMQ special case that admits $O(n)/O(1)$.

RMQ → LCA. Build the Cartesian tree of the array (a heap by value, a BST by index); then $\mathrm{RMQ}(l,r)$ is the value at $\mathrm{LCA}(l,r)$ in that tree.

// Cartesian tree in O(n) with a monotonic stack
vector<int> par(n, -1), st;
for (int i = 0; i < n; i++) {
    int last = -1;
    while (!st.empty() && a[st.back()] > a[i]) { last = st.back(); st.pop_back(); }
    if (!st.empty()) par[i] = st.back();
    if (last != -1) par[last] = i;
    st.push_back(i);
}

This equivalence is why the $O(n)/O(1)$ result for ±1 RMQ gives $O(n)/O(1)$ for general RMQ: reduce to LCA, then back to ±1 RMQ.

The $O(n)$ / $O(1)$ construction

1. Split into blocks of size $b=\frac{1}{2}{\log }_{2}n$.
2. Sparse table over the $n/b$ block minima: $O\left(\frac{n}{b}\log \frac{n}{b}\right)=O(n)$.
3. Within a block, the ±1 structure means only $2^{b-1}=O(\sqrt{n})$ distinct block types exist; precompute every internal query for each type: $o(n)$.
4. A query = suffix of one block + whole blocks + prefix of another.

See Farach-Colton-Bender. The constant is large; the $O(n\log n)$ sparse table beats it for every realistic $n$.

Variants

Variant	Method
Range max	same, flip the comparison
Range gcd	sparse table (gcd is idempotent), $O(\log )$ per merge
Range sum	prefix sum
With updates	segment tree
Range min index	store indices in the table
$k$-th smallest in a range	different problem — persistent segment tree
Min over a tree path	binary lifting or HLD
2D range min	2D sparse table ($O(nm\log n\log m)$ memory) or per-row tables
Min over all subarrays of a fixed length	monotonic deque, $O(n)$

Where RMQ appears as a subroutine

• LCP of arbitrary suffixes — RMQ over the LCP array;
• LCA — via the Euler tour;
• Divide and conquer on the minimum — “for each subarray, the minimum splits it” (used in the largest rectangle and Cartesian tree DPs);
• Range queries in D&C DP.

See also: Sparse Table · LCA · Farach-Colton-Bender