Range Minimum Query

Range minimum query (abbreviated RMQ) is a fundamental indexing problem and static data-structural primitive within computation and algorithms that preprocesses an array A[0 .. n − 1] of n totally ordered elements so that, given any pair of indices 0 ≤ i ≤ j < n, the query RMQ_A(i, j) returns the index k ∈ [i, j] of a minimum element in the contiguous subarray A[i .. j]:

While a naive scan takes O(j − i + 1) = O(n) time and a precomputed two-dimensional lookup table over all (i, j) pairs requires Θ(n²) space, classical reductions by Gabow, Bentley, and Tarjan (1984), Berkman and Vishkin (1993), Michael A. Bender and Martin Farach-Colton (2000), and Johannes Fischer and Volker Heun (2011) establish that any static array of n elements can be preprocessed in linear O(n) time to answer every range minimum query in worst-case O(1) time. Furthermore, Fischer and Heun proved that the index can be encoded as a succinct data structure occupying 2n + o(n) bits of memory without even consulting the original array A at query time.

From LCA to ±1 RMQ via Euler Tour

The modern theory of range minimum queries rests on an algebraic and combinatorial equivalence between RMQ on arrays and the Lowest Common Ancestor (LCA) problem on rooted trees. Given a rooted tree T with n nodes, the lowest common ancestor LCA_T(u, v) of two nodes u and v is the deepest node in T that is an ancestor of both u and v.

An Euler tour of T starts at the root and traverses every tree edge twice (once downward, once upward), visiting a sequence of 2n − 1 vertices stored in an Euler tour array E[0 .. 2n − 2], along with a corresponding depth array D[0 .. 2n − 2] where D[t] is the tree depth of vertex E[t], and a first-occurrence array F[u] recording the first index t where E[t] = u.

For any two vertices u and v with F[u] ≤ F[v], the Euler tour must visit LCA_T(u, v) at least once between step F[u] and step F[v], and can never rise to a shallower ancestor of LCA_T(u, v) before finishing the subtree rooted at LCA_T(u, v). Therefore, the lowest common ancestor of u and v is the unique shallowest vertex visited in the subarray E[F[u] .. F[v]]:

Crucially, because every step in an Euler tour moves from a node either to one of its children (depth + 1) or to its parent (depth − 1), adjacent entries in the depth array D always differ by +1 or −1:

This constrained problem is known as ±1 RMQ.

From General RMQ to LCA via the Cartesian Tree

Conversely, any general array A[0 .. n − 1] of arbitrary comparable numbers can be reduced to LCA (and hence to ±1 RMQ) in linear O(n) time by constructing the Cartesian tree C(A) introduced by Jean Vuillemin in 1980:

• The root of C(A) is the index m = RMQ_A(0, n − 1) of the global minimum element of A.
• The left subtree of m is recursively the Cartesian tree of the prefix subarray A[0 .. m − 1], and the right subtree of m is the Cartesian tree of the suffix subarray A[m + 1 .. n − 1].

By construction, an in-order traversal of C(A) recovers the array indices 0, 1, …, n − 1 in sorted order, while the tree satisfies the min-heap property with respect to values in A. Consequently, for any query range [i, j], the unique index k ∈ [i, j] minimizing A[k] is the lowest common ancestor of nodes i and j in the Cartesian tree C(A):

Using a monotone stack that scans A from left to right and climbs the rightmost spine of the tree built so far, each element is pushed onto and popped from the rightmost spine at most once, constructing C(A) in O(n) time. Taking the Euler tour of C(A) reduces any general RMQ instance of size n to a ±1 RMQ instance of size 2n − 1 in linear time!

Power-of-Two Sparse Table (⟨O(n log n), O(1)⟩)

Before applying block compression, the key building block for constant-time range queries is the Sparse Table (Bender and Farach-Colton, 2000). Because the minimum operation is idempotent—meaning min(X, Y) equals min(X, Y) even when two intervals X and Y overlap—any range [i, j] of length L = j − i + 1 can be covered by two overlapping intervals of power-of-two length 2^k, where k = ⌊log₂(j − i + 1)⌋:

If we precompute a table M[i][k] = RMQ_A(i, i + 2^k − 1) for all 0 ≤ i < n and 0 ≤ k ≤ ⌊log₂ n⌋ by dynamic programming in O(n log n) time and space, then any query RMQ_A(i, j) is answered in O(1) time by comparing just two array entries: M[i][k] and M[j − 2^k + 1][k].

Four Russians Block Decomposition for Linear Preprocessing

To reduce the Sparse Table's preprocessing cost from O(n log n) down to O(n) on the ±1 Euler-depth array D[0 .. N − 1] (where N = 2n − 1), Bender and Farach-Colton apply the Method of Four Russians by partitioning D into N / b contiguous micro-blocks of size b = ⌊(1/2) log₂ N⌋:

1. Inter-Block Macro-Array: Form a reduced array B[0 .. N/b − 1] of length N / b storing the minimum of each micro-block, and build a standard power-of-two Sparse Table over B. Because B has length O(n / log n), building its Sparse Table takes O((n / log n) · log(n / log n)) = O(n) time and space!
2. Intra-Block Normalized Lookup Table: Within any micro-block of length b, subtracting the block's first element D[t₀] yields a normalized relative sequence starting at 0 whose adjacent differences are in {+1, −1}. Thus, every normalized micro-block is completely determined by a binary vector of b − 1 step signs (+1 or −1). Because there are only 2^b−1 ≤ 2^{(1/2) log₂ N} = √N distinct normalized block types, precomputing all O(b²) pairwise answers for every possible block type requires only O(√n · log² n) = o(n) time and space!

Any query RMQ_D(i, j) decomposes into at most two intra-block queries (at the partial left and right boundary blocks, answered in O(1) time via the normalized lookup table) and one contiguous inter-block query over B (answered in O(1) time via the macro Sparse Table).

Because there are C_n = (1 / (n + 1)) · (2n choose n) ≈ 4ⁿ / (√π n^3/2) distinct Cartesian trees on n elements—and two arrays have identical RMQ answers for all pairs (i, j) if and only if they have the same Cartesian tree—the information-theoretic minimum space required to answer RMQ(i, j) without reading A is log₂(C_n) = 2n − Θ(log n) bits.

In 2011, Johannes Fischer and Volker Heun achieved this information-theoretic bound directly in O(n) construction time and 2n + o(n) bits without converting to an Euler tour (which would double the tree to 2n − 1 nodes and cost 4n bits). They converted the Cartesian tree into a 2D-Min-Heap represented by its Depth-First Unary Degree Sequence (DFUDS) balanced-parentheses bitvector of length 2n bits, answering LCA queries directly on the succinct balanced-parentheses bitvector in O(1) time.

Range minimum queries serve as the backbone of modern string indexing. When a suffix array SA[0 .. n − 1] is paired with its Longest Common Prefix (LCP) array LCP[1 .. n − 1] (where LCP[r] is the length of the longest common prefix between lexicographically adjacent suffixes SA[r − 1] and SA[r]), the longest common prefix between any two arbitrary suffixes of a text at positions p and q (with inverse ranks i = ISA[p] < j = ISA[q]) is given by a single constant-time range minimum query over the LCP array:

Why can't the Sparse Table trick be used for Range Sum Queries in O(1) time?

A Sparse Table covers a query interval [i, j] using two overlapping intervals [i, i + 2^k − 1] and [j − 2^k + 1, j]. This works for operations that are idempotent (x ⊕ x = x), such as minimum, maximum, greatest common divisor (gcd), least common multiple (lcm), and bitwise AND/OR, because counting the middle overlap twice does not change the answer. Addition is not idempotent, though static range sum queries are even simpler: a single linear-space prefix-sum array P[k] = ∑_{t < k} A[t] answers any range sum in O(1) time via P[j + 1] − P[i]. For non-idempotent non-invertible associative operations (arbitrary semigroups), Disjoint Sparse Tables or Sqrt Trees achieve O(1) query time in O(n log n) space.

How does RMQ handle duplicate minimum values in A?

To guarantee a unique Cartesian tree and a canonical tie-breaking rule between RMQ and LCA, ties in A are broken consistently—typically by choosing the leftmost minimum index: A[p] ≺ A[q] if and only if A[p] < A[q] or (A[p] = A[q] and p < q).

What if array elements are updated dynamically?

In the dynamic setting where point updates A[k] ← v are interleaved with RMQ(i, j) queries, Mihai Pătraşcu and Erik Demaine (2006) proved an Ω(log n / log log n) cell-probe lower bound per operation, which is matched in practice by a segment tree in O(log n) time for both point updates and range minimum queries.

1. Bender, M. A., & Farach-Colton, M. (2000). "The LCA problem revisited." In Proceedings of the 4th Latin American Symposium on Theoretical Informatics (LATIN 2000), Lecture Notes in Computer Science, vol. 1776, 88–94. https://doi.org/10.1007/10719839-9
2. Fischer, J., & Heun, V. (2011). "Space-efficient preprocessing schemes for range minimum queries on static arrays." SIAM Journal on Computing, 40(2), 465–492. https://doi.org/10.1137/090779759
3. Berkman, O., & Vishkin, U. (1993). "Recursive star-tree parallel data structure." SIAM Journal on Computing, 22(2), 221–242. https://doi.org/10.1137/0222017
4. Gabow, H. N., Bentley, J. L., & Tarjan, R. E. (1984). "Scaling and related techniques for geometry problems." In Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing (STOC '84), 135–143. https://doi.org/10.1145/800057.808675