← all categories

Sparse Table 0a74c0ca

Sparse table for static range queries over an idempotent, associative op (default min). Edit comb() for a different op.

Time: O(n \log n) build, O(1) query. tested

content/data-structures/sparse-table.h

template <typename T>
struct SparseTable {
    vector<vector<T>> table;
    int n, logn;

    T comb(T a, T b) { return min(a, b); }  // op: edit for a different idempotent op

    SparseTable(vector<T> &a) : n(a.size()) {
        logn = 1;
        while ((1 << logn) <= n) logn++;
        table.assign(logn, vector<T>(n));
        table[0] = a;
        for (int j = 1; j < logn; j++)
            for (int i = 0; i + (1 << j) <= n; i++)
                table[j][i] = comb(table[j - 1][i], table[j - 1][i + (1 << (j - 1))]);
    }

    T query(int l, int r) {  // inclusive [l, r]
        int j = 31 - __builtin_clz(r - l + 1);
        return comb(table[j][l], table[j][r - (1 << j) + 1]);
    }
};