Range Minimum Query (Sparse Table) - Algorithm Tutorial | Repovive

Range Minimum Query (Sparse Table) Algorithm Tutorial

mediumdata structures2 min read

Introduction

The Range Minimum Query (RMQ) problem asks: given an array $A$ and multiple queries, find the minimum element in a specified range $[l, r]$ for each query.

Naive approach: For each query, scan from $l$ to $r$ and find the minimum. This takes $O(r - l + 1)$ per query, or $O(nq)$ total for $q$ queries.

Challenge: With $n, q \le 10^5$ , the naive approach is too slow. We need $O(1)$ or $O(\log n)$ per query.

Applications:

Finding lowest common ancestor (LCA) in trees
Suffix array construction
Competitive programming (frequent query pattern)
Database query optimization

Sparse Table Concept

A Sparse Table preprocesses the array so each query can be answered in $O(1)$ time.

Key Insight: Any range can be covered by at most 2 overlapping ranges whose lengths are powers of 2.

For minimum queries, overlapping is fine because $\min(\min(A), \min(B)) = \min(A \cup B)$ .

Table Definition: Let $sparse[i][j] =$ minimum of the range starting at index $i$ with length $2^j$ .

Range Coverage: For a query $[l, r]$ :

Find the largest $k$ such that $2^k \le r - l + 1$
The range $[l, r]$ is covered by $[l, l + 2^k - 1]$ and $[r - 2^k + 1, r]$
Answer = $\min(sparse[l][k], sparse[r - 2^k + 1][k])$

These two ranges overlap but together cover $[l, r]$ completely.

Building the Table

Preprocessing: $O(n \log n)$

Build the sparse table using dynamic programming:

text

function build_sparse_table(arr):
    n = length(arr)
    LOG = floor(log2(n)) + 1

    // Base case: ranges of length 1
    for i from 0 to n-1:
        sparse[i][0] = arr[i]

    // Fill table for increasing powers of 2
    for j from 1 to LOG-1:
        for i from 0 to n - 2^j:
            sparse[i][j] = min(sparse[i][j-1],
                               sparse[i + 2^(j-1)][j-1])

Recurrence Explanation: A range of length $2^j$ is the minimum of two adjacent ranges of length $2^{j-1}$ : $sparse[i][j] = \min(sparse[i][j-1], sparse[i + 2^{j-1}][j-1])$

Space: $O(n \log n)$

Answering Queries

Query: $O(1)$

text

function query(l, r):
    len = r - l + 1
    k = floor(log2(len))
    return min(sparse[l][k], sparse[r - 2^k + 1][k])

Example: Array $[3, 1, 4, 1, 5, 9, 2, 6]$ , query $[2, 6]$ (0-indexed: $[1, 5]$ )

Length = $5$
$k = \lfloor \log_2(5) \rfloor = 2$ (since $2^2 = 4 \le 5$ )
Left range: $[1, 1 + 4 - 1] = [1, 4]$
Right range: $[5 - 4 + 1, 5] = [2, 5]$
Answer = $\min(sparse[1][2], sparse[2][2])$

Precompute logs: To avoid computing $\lfloor \log_2 \rfloor$ each query, precompute an array:

text

log[1] = 0
for i from 2 to n:
    log[i] = log[i/2] + 1

Implement this Algorithm

Go to Problem

Related Algorithms

2D Difference Painting

Complexity Analysis

Time Complexity:

Preprocessing: $O(n \log n)$
Each query: $O(1)$
Total for $q$ queries: $O(n \log n + q)$

Space Complexity: $O(n \log n)$

Comparison with other approaches:

Approach	Preprocessing	Query	Space
Naive	$O(1)$	$O(n)$	$O(1)$
Sparse Table	$O(n \log n)$	$O(1)$	$O(n \log n)$
Segment Tree	$O(n)$	$O(\log n)$	$O(n)$
Block Decomposition	$O(n)$	$O(\sqrt{n})$	$O(\sqrt{n})$

When to use Sparse Table:

Many queries on a static array
Need the fastest possible query time
Space is not a critical constraint

Limitation: Sparse table does not support updates. For dynamic arrays, use a segment tree instead.