Sparse Table
(datastructure/sparsetable.hpp)

• View this file on GitHub
• Last update: 2020-08-25 17:20:34+09:00
• Include: #include "datastructure/sparsetable.hpp"

概要

静的な数列に対する区間取得クエリを定数時間で答えられるデータ構造.

渡す二項演算$f$は結合律と冪等律を満たす必要がある.

• 結合律 : $f(f(x, y), z) = f(x, f(y, z))$
• 冪等律 : $f(x, x) = x$

計算量

• 構築 : $O(n\log n)$
• 区間取得 : $O(1)$

使用例

• SparseTable<int> st(v, [](int a, int b){ return min(a, b); }) : 区間最小クエリを処理するSparse Tableを構築.
• st.query(l, r) : 半開区間$[l, r)$の区間取得クエリ.

Verified with

• test/yosupo/staticrmq.test.cpp

Code

/**
* @brief Sparse Table
* @docs docs/datastructure/sparsetable.md
*/

template <typename T>
struct SparseTable {
    vector<vector<T>> st;
    using F = function<T(T, T)>;
    const F f;
    SparseTable() {}
    SparseTable(const vector<T> &v, const F f)
        : f(f) {
        int b = 0, sz = v.size();
        while ((1 << b) <= sz) ++b;
        st.assign(b, vector<T>(1 << b));
        for (int i = 0; i < sz; ++i) st[0][i] = v[i];
        for (int i = 1; i < b; ++i) {
            for (int j = 0; j + (1 << i) <= (1 << b); ++j) {
                st[i][j] = f(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
            }
        }
    }
    T query(const int l, const int r) const {
        int b = 31 - __builtin_clz(r - l);
        return f(st[b][l], st[b][r - (1 << b)]);
    }
};

#line 1 "datastructure/sparsetable.hpp"
/**
* @brief Sparse Table
* @docs docs/datastructure/sparsetable.md
*/

template <typename T>
struct SparseTable {
    vector<vector<T>> st;
    using F = function<T(T, T)>;
    const F f;
    SparseTable() {}
    SparseTable(const vector<T> &v, const F f)
        : f(f) {
        int b = 0, sz = v.size();
        while ((1 << b) <= sz) ++b;
        st.assign(b, vector<T>(1 << b));
        for (int i = 0; i < sz; ++i) st[0][i] = v[i];
        for (int i = 1; i < b; ++i) {
            for (int j = 0; j + (1 << i) <= (1 << b); ++j) {
                st[i][j] = f(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
            }
        }
    }
    T query(const int l, const int r) const {
        int b = 31 - __builtin_clz(r - l);
        return f(st[b][l], st[b][r - (1 << b)]);
    }
};

Back to top page