Sparse Table

Static range query structure — O(1) for idempotent operations (min/max/gcd), O(log n) for non-idempotent.

[Range Queries]|

Jul 9, 2026

|explanatory_notes.md|

#sparse-table#rmq#range-minimum#static

$cat source_code/

cpp

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 5;
const int LOG = 18;
int table[MAXN][LOG];
int lg[MAXN];
int n;

int combine(int a, int b) { return min(a, b); }

void build(int a[]) {
    for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
    for (int i = 1; i <= n; i++) table[i][0] = a[i];
    for (int j = 1; j < LOG; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            table[i][j] = combine(table[i][j-1], table[i + (1 << (j-1))][j-1]);
}

int query(int l, int r) {
    int k = lg[r - l + 1];
    return combine(table[l][k], table[r - (1 << k) + 1][k]);
}

int queryNonIdempotent(int l, int r) {
    int ans = 0;
    for (int j = LOG - 1; j >= 0; j--) {
        if (l + (1 << j) - 1 <= r) {
            ans = combine(ans, table[l][j]);
            l += 1 << j;
        }
    }
    return ans;
}

34 linesutf-8

$cat explanation_notes.md

notes_viewer --renderedmarkdown (math enabled)

Sparse Table

Static data structure for range queries on immutable arrays. $O(1)$ for idempotent operations, $O(\log n)$ for non-idempotent.

How It Works

Precompute:

\text{table}[i][j] = \text{op}(\text{table}[i][j-1],\; \text{table}[i + 2^{j-1}][j-1])

Each entry covers a range of length

2^j

starting at

i

$O(1)$ Query (min, max, gcd)

For idempotent operations where $\text{op}(x, x) = x$ :

\text{query}(l, r) = \text{op}(\text{table}[l][p],\; \text{table}[r - 2^p + 1][p])

where $p = \lfloor \log_2(r - l + 1) \rfloor$ . Two overlapping intervals cover $[l, r]$ — overlap is safe for idempotent ops.

$O(\log n)$ Query (sum)

For non-idempotent operations, iterate through powers of two without overlap.

When to Use

Static array, no updates

RMQ (range minimum query)

Faster than segment tree for static queries

Complexity

Build —

O(n \log n)

Query —

O(1)

idempotent,

O(\log n)

non-idempotent

Space —

O(n \log n)

Sparse Table

Sparse Table

How It Works

O(1)O(1)O(1) Query (min, max, gcd)

O(log⁡n)O(\log n)O(logn) Query (sum)

When to Use

Complexity

$O(1)$ Query (min, max, gcd)

$O(\log n)$ Query (sum)