uniolympiads Ελληνικά

Sparse table

Range minimum on a static array in O(1)O(1), after O(nlog⁡n)O(n \log n) preprocessing.

When

The array does not change and there are very many queries, or the query sits inside another loop (e.g. inside a binary search), so the log⁡n\log n of a segment tree matters.

The idea

stk[i]=min⁡(ai,…,ai+2k−1)\mathrm{st}_k[i] = \min(a_i, \dots, a_{i + 2^k - 1}). Level kk is built from level k−1k-1 out of two halves: stk[i]=min⁡(stk−1[i],stk−1[i+2k−1])\mathrm{st}_k[i] = \min(\mathrm{st}_{k-1}[i], \mathrm{st}_{k-1}[i + 2^{k-1}]).

For a query [l,r][l, r] of length L=r−l+1L = r - l + 1, take k=⌊log⁡2L⌋k = \lfloor \log_2 L \rfloor. The two blocks of length 2k2^k, one from the start and one from the end, cover the whole range. They overlap, but that does not matter for the minimum:

min⁡(al,…,ar)=min⁡(stk[l], stk[r−2k+1]).\min(a_l, \dots, a_r) = \min\bigl(\mathrm{st}_k[l],\ \mathrm{st}_k[r - 2^k + 1]\bigr).

The same holds for every operation with x∘x=xx \circ x = x: maximum, gcd, and, or. Not for sums, where the overlap is counted twice.

Pitfalls

  • Compute the logarithms once into an array (lg[i] = lg[i / 2] + 1), not with log2 on doubles inside the query.
  • Memory is nlog⁡nn \log n: for n=2⋅105n = 2 \cdot 10^5 that is about 3.6⋅1063.6 \cdot 10^6 values, 29 MB as long long. With a 256 MB limit you are fine; with 64 MB, be careful.

Code

No main: it goes below the #include lines, using namespace std and using ll = long long.

cpp/sparse-table.cpp
// Sparse table for range minimum on a static array.
// Build O(n log n), query O(1): [l, r] is covered by two overlapping blocks of length 2^k.
// Works for any idempotent operation (min, max, gcd), not for sums.

struct SparseTable {
    vector<vector<ll>> st;
    vector<int> lg;

    SparseTable(const vector<ll>& a) {
        int n = a.size();
        lg.assign(n + 1, 0);
        for (int i = 2; i <= n; i++) {
            lg[i] = lg[i / 2] + 1;
        }
        int levels = lg[max(n, 1)] + 1;
        st.assign(levels, vector<ll>(n));
        for (int i = 0; i < n; i++) {
            st[0][i] = a[i];
        }
        for (int k = 1; k < levels; k++) {
            for (int i = 0; i + (1 << k) <= n; i++) {
                st[k][i] = min(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
            }
        }
    }

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

Tested on 1,000 random cases against a slow, obviously correct solution, with AddressSanitizer and UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).

Practice on CSES

In order: the first is the plain application, the rest need a twist.