Sparse Table (sparse_table.hpp)

結合法則・冪等性を満たす演算についての更新無し区間クエリを処理する。

コンストラクタ

SparseTable(const vector<S>& v)

数列 v で構築する。

計算量

$O(N\log N)$

prod

S prod(int l, int r)

区間 $[l, r)$ の総積を返す。

計算量

$O(1)$

Required by

Verified with

test/lc_staticrmq.cpp

Code

template <typename S, auto op>
class SparseTable {
    static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>, "op must work as S(S, S)");

   public:
    explicit SparseTable(const vector<S>& v) : n(v.size()), log_table(n + 1) {
        for (int i = 2; i < n + 1; ++i) {
            log_table[i] = log_table[i >> 1] + 1;
        }

        table.resize(log_table[n] + 1, vector<S>(n));

        for (int i = 0; i < n; ++i) {
            table[0][i] = v[i];
        }

        for (int i = 1; (1 << i) <= n; ++i) {
            for (int j = 0; j + (1 << i) <= n; ++j) {
                table[i][j] = op(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
            }
        }
    }

    S prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= n);
        const int k = log_table[r - l];

        return op(table[k][l], table[k][r - (1 << k)]);
    }

   private:
    int n;

    vector<int> log_table;
    vector<vector<S>> table;
};

#line 1 "sparse_table.hpp"
template <typename S, auto op>
class SparseTable {
    static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>, "op must work as S(S, S)");

   public:
    explicit SparseTable(const vector<S>& v) : n(v.size()), log_table(n + 1) {
        for (int i = 2; i < n + 1; ++i) {
            log_table[i] = log_table[i >> 1] + 1;
        }

        table.resize(log_table[n] + 1, vector<S>(n));

        for (int i = 0; i < n; ++i) {
            table[0][i] = v[i];
        }

        for (int i = 1; (1 << i) <= n; ++i) {
            for (int j = 0; j + (1 << i) <= n; ++j) {
                table[i][j] = op(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
            }
        }
    }

    S prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= n);
        const int k = log_table[r - l];

        return op(table[k][l], table[k][r - (1 << k)]);
    }

   private:
    int n;

    vector<int> log_table;
    vector<vector<S>> table;
};