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

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/algorithms/rmq-sparse-table

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/algorithms/rmq-sparse-table

Repovive

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

+

1

)

O(r - l + 1)

Building the Table

Preprocessing: $O(n \log n)$

Build the sparse table using dynamic programming:

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)$

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$ )

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

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

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

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.

O(n \log n)

Range Minimum Query (Sparse Table) Algorithm Tutorial

Introduction

Practice this Algorithm

Related Algorithms

Sparse Table Concept

Building the Table

Answering Queries

Complexity Analysis