src/DataStructure/SparseTable.hpp

View this file on GitHub
Last update: 2020-07-13 00:16:00+09:00
Include: #include "src/DataStructure/SparseTable.hpp"

概要

冪等性を持つモノイドについて、区間畳み込みを高速に計算する。構築O(n log n), クエリO(1)

アルゴリズム

構築時には各点から始まるダブリングを計算。クエリ時には、始点と終点からそれぞれ最も長い計算済みの区間を持ってきて(これはMSBから求まる)、2つの合成を求める。 2つの区間にはかぶりが生じるが、冪等性を仮定していることから正しい答えが求まることが保証される。

Verified with

test/yosupo/staticrmq_sparse_table.test.cpp

Code

/// @docs src/DataStructure/SparseTable.md
template <class T, class F> struct SparseTable {
    const F op;
    std::vector<std::vector<T>> t;
    SparseTable(F op_, const std::vector<T>& a) : op(op_), t({a}) {
        for (int k = 1; 1 << k < a.size() + 1; k++) {
            t.emplace_back(a.size() - (1 << k) + 1);
            for (int i = 0; i < a.size() - (1 << k) + 1; i++) {
                t[k][i] = op(t[k - 1][i], t[k - 1][i + (1 << (k - 1))]);
            }
        }
    }
    T query(int l, int r) const {
        assert(0 <= l && l < r && r <= t[0].size());
        int k = std::__lg(r - l);
        return op(t[k][l], t[k][r - (1 << k)]);
    }
};
template <class T, class F> auto make_sparse_table(F op, const std::vector<T>& a) { return SparseTable<T, F>(op, a); }

#line 1 "src/DataStructure/SparseTable.hpp"
/// @docs src/DataStructure/SparseTable.md
template <class T, class F> struct SparseTable {
    const F op;
    std::vector<std::vector<T>> t;
    SparseTable(F op_, const std::vector<T>& a) : op(op_), t({a}) {
        for (int k = 1; 1 << k < a.size() + 1; k++) {
            t.emplace_back(a.size() - (1 << k) + 1);
            for (int i = 0; i < a.size() - (1 << k) + 1; i++) {
                t[k][i] = op(t[k - 1][i], t[k - 1][i + (1 << (k - 1))]);
            }
        }
    }
    T query(int l, int r) const {
        assert(0 <= l && l < r && r <= t[0].size());
        int k = std::__lg(r - l);
        return op(t[k][l], t[k][r - (1 << k)]);
    }
};
template <class T, class F> auto make_sparse_table(F op, const std::vector<T>& a) { return SparseTable<T, F>(op, a); }