ii. Range Minimum Query

RMQ on a static array is equivalent to LCA on a tree: an RMQ is an LCA in the Cartesian tree, and an LCA is a $\pm 1$ RMQ on the Euler tour depths. Both admit $O(n)$ preprocessing and $O(1)$ queries. In practice the sparse table is the default, the 64-word “linear RMQ” is the fast $O(n)$ choice, and offline queries can use a DSU sweep.

Methods

Method	Build	Query	Notes
naive rescan	$O(1)$	$O(n)$	fine for a handful of queries
precompute every range	$O(n^2)$	$O(1)$	$O(n^2)$ memory, only for $n\lesssim 2000$
sparse table	$O(n\log n)$	$O(1)$	the default (Sparse Table)
segment tree	$O(n)$	$O(\log n)$	supports updates
linear RMQ (64-bit masks + sparse table on blocks)	$O(n)$	$O(1)$	fast and light for $n$ up to $10^7$
Farach-Colton-Bender	$O(n)$	$O(1)$	theoretical; large constant
offline DSU sweep (Arpa’s trick)	$O((n+q)\alpha )$		all queries known
sqrt tree	$O(n\log \log n)$	$O(1)$	any associative op, with point updates (Sqrt)

Linear RMQ with bitmask stacks

For each $i$, mask[i] encodes the monotonic stack of the last 64 positions: bit $k$ means position $i-k$ is a suffix minimum of the window ending at $i$. A short range ending at $r$ is answered by the highest surviving bit within its length. Longer ranges take two such answers plus a sparse table over blocks of 64.

template<class T, class Cmp = less<T>> struct LinearRMQ {
    int n; vector<T> v; vector<ull> mask; vector<int> sp; Cmp cmp;
    int better(int x, int y) const { return cmp(v[x], v[y]) ? x : y; }
    static int msb(ull x) { return 63 - __builtin_clzll(x); }
    int small(int r, int len = 64) const { return r - msb(len == 64 ? mask[r] : mask[r] & ((1ULL << len) - 1)); }
    LinearRMQ(const vector<T>& a, Cmp c = Cmp()) : n(sz(a)), v(a), mask(n), cmp(c) {
        ull at = 0;
        for (int i = 0; i < n; i++) {
            at <<= 1;
            while (at && better(i, i - msb(at & -at)) == i) at ^= at & -at;
            mask[i] = at |= 1;
        }
        int b = n / 64; if (!b) return;
        int L = __lg(b) + 1; sp.assign(b * L, 0);
        for (int i = 0; i < b; i++) sp[i] = small(64 * i + 63);
        for (int j = 1; j < L; j++) for (int i = 0; i + (1 << j) <= b; i++)
            sp[b * j + i] = better(sp[b * (j - 1) + i], sp[b * (j - 1) + i + (1 << (j - 1))]);
    }
    int argmin(int l, int r) const {               // [l, r)
        r--;
        if (r - l + 1 <= 64) return small(r, r - l + 1);
        int ans = better(small(l + 63), small(r)), x = l / 64 + 1, y = r / 64 - 1;
        if (x <= y) { int j = __lg(y - x + 1), b = n / 64; ans = better(ans, better(sp[b * j + x], sp[b * j + y - (1 << j) + 1])); }
        return ans;
    }
    T query(int l, int r) const { return v[argmin(l, r)]; }
};

Proof: the bitmask stack and linear RMQ are correct

Invariant on mask[i]: bit $k$ of mask[i] is set iff $i-k$ is a suffix minimum of the window $[i-k,i]$, i.e. $a[i-k]$ is better-or-equal to every element of $(i-k,i]$ — the same monotonic-stack invariant proved for the sliding-window deque in Two Pointers. Induction on $i$: shifting left ages every bit by one position (offset $k\to k+1$, still correctly describing suffix minima of the old window relative to the new right end, since no element to the left of $i$ changed), then the while loop removes exactly the closest surviving positions that are no longer suffix minima once $i$ is included (those with $a[j]$ worse than $a[i]$ — if $j$ survived meant $a[j]\le$ everything in $(j,i)$, and now either $a[i]\le a[j]$, in which case $j$ stops being a suffix minimum once $i$ joins, or $a[i]>a[j]$, in which case $j$ remains valid and the loop correctly stops there since positions are processed closest-first — the lowest surviving bit is the one closest to $i$), and finally setting bit 0 records that $i$ itself is trivially a suffix minimum of $[i,i]$. small(r,len) returns $r-\text{msb}(\text{mask}[r]\&(2^{len}-1))$, i.e. the farthest surviving suffix-minimum position within the last $len$ entries; by the invariant, surviving positions have values that are non-increasing as you move farther from $r$ (each survived because it beat everything closer), so the farthest survivor within the window is the minimum of the whole window $[r-len+1,r]$. argmin for $r-l+1\le 64$ calls small directly; for longer ranges it takes small of the partial first/last blocks of 64 plus a sparse table over complete 64-blocks (correct by the sparse-table proof above, since whole-block minima are idempotent under better), and takes the best of all three — covering $[l,r)$ exactly once each piece, so the overall min is correct. $■$

Tested against min_element on 2000 random arrays (size up to 300) and 20 random ranges each — all match.

Proof: Arpa's offline DSU sweep is correct

Key fact at the moment $a[r]$ pops $j$ (because $a[r]<a[j]$, and $j$ was on the monotonic stack, meaning $a[j]\le a[j+\mathrm{1..}r-1]$): then $a[r]=\min (a[j..r])$, since $a[r]<a[j]\le a[j+\mathrm{1..}r-1]$. Setting p[j] = r therefore records that, from this point on, $j$ and $r$ are interchangeable range-starts: for any $r^{\prime \prime }\ge r$, $\min (a[j..r^{\prime \prime }])=\min (a[r..r^{\prime \prime }])$, because $a[j..r]$‘s minimum is already $a[r]$, so prepending $a[j..r-1]$ to $a[r..r^{\prime \prime }]$ changes nothing. So each union link is a sound “this start point can be redirected to that one without changing the answer for any later right endpoint” step. Induction on the find chain: find(l) follows these links until reaching a position $l^{\ast }$ with p[l^*] = l^*, i.e. $l^{\ast }$ is still on the stack at time $r$ — meaning $a[l^{\ast }]\le a[l^{\ast }+\mathrm{1..}r]$ by the stack invariant, so $a[l^{\ast }]=\min (a[l^{\ast }..r])$. By the key fact applied transitively along the chain $l\to \cdots \to l^{\ast }$, $\min (a[l..r])=\min (a[l^{\ast }..r])=a[l^{\ast }]$, so $l^{\ast }$ is exactly $\arg \min a[l..r]$. $■$

Tested against min_element on 2000 random arrays (size up to 50) with random query batches — all match.

RMQ and LCA

• LCA $\to$ $\pm 1$ RMQ: in the Euler tour depth array consecutive values differ by exactly 1, so a block of length $b=\frac{1}{2}\log n$ has one of $2^{b-1}=O(\sqrt{n})$ shapes. Precompute every in-block answer for every shape, a sparse table over blocks (cost $O\left(\frac{m}{b}\log \frac{m}{b}\right)=O(m)$ for $m=2n-1$ tour entries), and a query splits into a prefix of one block, some whole blocks, and a suffix of another — three $O(1)$ lookups. That’s Farach-Colton-Bender: $O(n)$/$O(1)$, large constant, rarely worth the code. The “precompute every shape” trick is called four Russians (Arlazarov, Dinic, Kronrod, Faradzhev — originally for boolean matrix multiplication), and the same idea reappears in bitset DP and precomputed popcount tables.
• RMQ $\to$ LCA: build the Cartesian tree in $O(n)$ with a monotonic stack. $\min a[l..r]$ is the value at $\mathrm{LCA}(l,r)$. So general RMQ is $O(n)$/$O(1)$ too.
• In practice for LCA: Euler tour + sparse table (fast, $O(1)$), or binary lifting when you also need $k$-th ancestors or path aggregates (LCA).

LCA method	Preprocess	Query	Note
naive climbing	$O(n)$	$O(n)$	fine for tiny trees
binary lifting	$O(n\log n)$	$O(\log n)$	the contest default — short, flexible, supports path queries
Euler tour + sparse table	$O(n\log n)$	$O(1)$	~15 lines, excellent constant — what to actually write when $O(1)$ matters
Tarjan offline (DSU)	$O((n+q)\alpha )$	amortized	needs every query known in advance
Farach-Colton-Bender	$O(n)$	$O(1)$	asymptotically optimal, large constant
Schieber–Vishkin	$O(n)$	$O(1)$	also optimal, bit-trick based, smaller constant than FCB in practice

$n\log n$ with a tiny constant beats $O(n)$ with a huge one for every $n$ a contest will throw at you — reach for binary lifting by default, Euler tour + sparse table when $O(1)$ queries matter, and FCB/Schieber–Vishkin only when profiling says so.

Proof: both reductions are correct

LCA $\to$ RMQ. Let first[v] be the index of $v$‘s first occurrence in the Euler tour, and let $d$ be the tour’s depth array. Every vertex on the path from $u$ to $\mathrm{LCA}(u,v)$ (and from $v$ up to it) appears in the tour between first[u] and first[v], each at depth $\ge \mathrm{depth}(\mathrm{LCA}(u,v))$ (every ancestor of $u$ or $v$ visited in that window is itself an ancestor of, or equal to, $\mathrm{LCA}(u,v)$, hence at depth $\ge$ it), and $\mathrm{LCA}(u,v)$ itself is visited at least once in that window at exactly its own depth. So $\min (d[\mathrm{first}[u]..\mathrm{first}[v]])=\mathrm{depth}(\mathrm{LCA}(u,v))$, achieved at an occurrence of $\mathrm{LCA}(u,v)$, giving $\mathrm{LCA}(u,v)$ itself via the argmin. Consecutive tour steps move to a parent or a child, changing depth by exactly $\pm 1$, which is the special structure Farach-Colton-Bender exploits for $O(1)$.
RMQ $\to$ LCA. Build the Cartesian tree (heap-ordered by value, BST-ordered by index — correctness of this $O(n)$ construction is proved in Monotonic Stack). For indices $l<r$, every index in $[l,r]$ is a descendant of $\mathrm{LCA}(l,r)$ in the Cartesian tree (BST order: the subtree rooted at any node spans a contiguous index range, and $l,r$‘s common subtree-range must contain $[l,r]$), and the heap property makes $\mathrm{LCA}(l,r)$‘s value $\le$ every value in its subtree, in particular $\le$ every $a_i$ for $i\in [l,r]$. Since $\mathrm{LCA}(l,r)$‘s own index lies in $[l,r]$ (it’s between its descendants $l$ and $r$ in BST order) and its value is a lower bound for the whole range, it must be the range minimum. $■$

Offline RMQ with a DSU (Arpa’s trick)

Sweep $r$. Keep the monotonic stack of suffix minima of $a[\mathrm{0..}r]$. When $a_r$ pops index $j$, attach $j$ to $r$ in a DSU. Then find(l) is the position of the minimum of $a[l..r]$.

vector<int> offlineArgmin(const vector<ll>& a, const vector<pair<int, int>>& qs) {   // [l, r)
    int n = sz(a); vector<vector<int>> at(n);
    for (int i = 0; i < sz(qs); i++) at[qs[i].second - 1].push_back(i);
    vector<int> p(n), st, res(sz(qs)); iota(all(p), 0);
    auto find = [&](int x) { while (p[x] != x) x = p[x] = p[p[x]]; return x; };
    for (int r = 0; r < n; r++) {
        while (!st.empty() && a[r] < a[st.back()]) p[st.back()] = r, st.pop_back();
        st.push_back(r);
        for (int i : at[r]) res[i] = find(qs[i].first);
    }
    return res;
}

Variants

Variant	Approach
range min with point updates	segment tree
range min with range add / assign	lazy segment tree
min over tree paths	binary lifting, HLD, or Kruskal reconstruction tree (for bottleneck queries)
min over every window of length $k$	monotonic deque, $O(n)$
position of the first element $<x$ to the right of $i$	segment tree descent, or binary lifting on the sparse table
number of distinct minima / count of minimum in range	segment tree storing (min, count)
2D range min	2D sparse table ($O(nm\log n\log m)$ memory, see Sparse Table) or per-row 1D tables

RMQ also shows up as a subroutine rather than the main problem: “for each subarray, the minimum splits it” divide-and-conquer (the same recursion that proves the largest-rectangle formula and builds the Cartesian tree), and range queries inside D&C DP.