Disjoint Sparse Table
(datastructure/disjoint_sparse_table.cpp)

• View this file on GitHub
• Last update: 2026-03-08 22:25:54+09:00

説明

結合則だけを満たす演算に対する静的区間クエリを処理する。 前計算 $O(N log N)$、クエリ $O(1)$。

できること

• DisjointSparseTable<F> dst(v) 配列 v から構築する
• void build(v) 配列 v で再構築する
• T query(int l, int r) 半開区間 [l, r) の積を返す。空区間なら F::e()

使い方

F に using T、static T f(T, T)、static T e() を定義して使う。 冪等性は不要で、結合則だけあればよい。

struct F {
    using T = int;
    static T f(T a, T b) { return min(a, b); }
    static T e() { return 1 << 30; }
};

DisjointSparseTable<F> dst(a);
int x = dst.query(l, r);

実装上の補足

query(l, r) は l == r のとき単位元を返す。 通常の sparse table より適用範囲は広いが、冪等演算だけなら SparseTable の方が軽い。

Verified with

• test/yosupo_staticrmq_disjoint_sparse_table.test.cpp

Code

template<class F>
struct DisjointSparseTable {
    using T = typename F::T;
    int n, lg;
    vector<vector<T>> table;

    DisjointSparseTable(): n(0), lg(0), table() {}
    explicit DisjointSparseTable(const vector<T> &v) { build(v); }

    void build(const vector<T> &v) {
        n = v.size();
        lg = 0;
        while ((1 << lg) < max(1, n)) ++lg;
        table.assign(lg + 1, vector<T>(n));
        if (n == 0) return;
        table[0] = v;
        for (int k = 1; k <= lg; ++k) table[k] = v;
        for (int k = 0; k < lg; ++k) {
            int len = 1 << k;
            for (int mid = len; mid < n; mid += len << 1) {
                int l = mid - len;
                int r = min(n, mid + len);
                table[k + 1][mid - 1] = v[mid - 1];
                for (int i = mid - 2; i >= l; --i) {
                    table[k + 1][i] = F::f(v[i], table[k + 1][i + 1]);
                }
                table[k + 1][mid] = v[mid];
                for (int i = mid + 1; i < r; ++i) {
                    table[k + 1][i] = F::f(table[k + 1][i - 1], v[i]);
                }
            }
        }
    }

    T query(int l, int r) const {
        if (l >= r) return F::e();
        --r;
        if (l == r) return table[0][l];
        int k = 31 - __builtin_clz(l ^ r);
        return F::f(table[k + 1][l], table[k + 1][r]);
    }
};

/**
 * @brief Disjoint Sparse Table
 */

#line 1 "datastructure/disjoint_sparse_table.cpp"
template<class F>
struct DisjointSparseTable {
    using T = typename F::T;
    int n, lg;
    vector<vector<T>> table;

    DisjointSparseTable(): n(0), lg(0), table() {}
    explicit DisjointSparseTable(const vector<T> &v) { build(v); }

    void build(const vector<T> &v) {
        n = v.size();
        lg = 0;
        while ((1 << lg) < max(1, n)) ++lg;
        table.assign(lg + 1, vector<T>(n));
        if (n == 0) return;
        table[0] = v;
        for (int k = 1; k <= lg; ++k) table[k] = v;
        for (int k = 0; k < lg; ++k) {
            int len = 1 << k;
            for (int mid = len; mid < n; mid += len << 1) {
                int l = mid - len;
                int r = min(n, mid + len);
                table[k + 1][mid - 1] = v[mid - 1];
                for (int i = mid - 2; i >= l; --i) {
                    table[k + 1][i] = F::f(v[i], table[k + 1][i + 1]);
                }
                table[k + 1][mid] = v[mid];
                for (int i = mid + 1; i < r; ++i) {
                    table[k + 1][i] = F::f(table[k + 1][i - 1], v[i]);
                }
            }
        }
    }

    T query(int l, int r) const {
        if (l >= r) return F::e();
        --r;
        if (l == r) return table[0][l];
        int k = 31 - __builtin_clz(l ^ r);
        return F::f(table[k + 1][l], table[k + 1][r]);
    }
};

/**
 * @brief Disjoint Sparse Table
 */

Back to top page