Sparse table
(sparse_table/sparse_table.hpp)

• View this file on GitHub
• Last update: 2021-11-02 23:36:31+09:00
• Include: #include "sparse_table/sparse_table.hpp"

Sparse table の実装．AC Library の Segtree と同様のインターフェース．前計算 $O(N \log N)$，クエリ $O(1)$．S の二項演算 op は結合法則と冪等性が成り立つ必要がある．

使用方法

S op(S l, S r);                 // 半群の元同士の演算．
vector<S> A(N);                 // 列．
sparse_table<S, op> st(A);
cout << st.prod(l, r) << '\n';  // 半開区間積クエリ．

問題例

• Library Checker: Static RMQ

Required by

• 2D sparse table (sparse_table/sparse_table_2d.hpp)

Verified with

• sparse_table/test/sparse_table.test.cpp
• sparse_table/test/sparse_table_2d.test.cpp
• sparse_table/test/sparse_table_aoj.test.cpp

Code

#pragma once
#include <cassert>
#include <vector>

// CUT begin
// Static sequence sparse table
// Complexity: O(NlogN) for precalculation, O(1) per query
template <class S, S (*op)(S, S), S (*e)()> struct sparse_table {
    int N, lgN;
    std::vector<std::vector<S>> d;
    std::vector<int> lgx_table;
    sparse_table() {}
    sparse_table(const std::vector<S> &sequence) : N(sequence.size()) {
        lgx_table.resize(N + 1);
        for (int i = 2; i < N + 1; ++i) lgx_table[i] = lgx_table[i >> 1] + 1;
        lgN = lgx_table[N] + 1;
        d.assign(lgN, std::vector<S>(N, e()));
        d[0] = sequence;
        for (int h = 1; h < lgN; ++h) {
            for (int i = 0; i + (1 << h) <= N; ++i) {
                d[h][i] = op(d[h - 1][i], d[h - 1][i + (1 << (h - 1))]);
            }
        }
    }
    S prod(int l, int r) const { // [l, r), 0-indexed
        assert(l >= 0 and r <= N);
        if (l >= r) return e();
        int h = lgx_table[r - l];
        return op(d[h][l], d[h][r - (1 << h)]);
    }
};

#line 2 "sparse_table/sparse_table.hpp"
#include <cassert>
#include <vector>

// CUT begin
// Static sequence sparse table
// Complexity: O(NlogN) for precalculation, O(1) per query
template <class S, S (*op)(S, S), S (*e)()> struct sparse_table {
    int N, lgN;
    std::vector<std::vector<S>> d;
    std::vector<int> lgx_table;
    sparse_table() {}
    sparse_table(const std::vector<S> &sequence) : N(sequence.size()) {
        lgx_table.resize(N + 1);
        for (int i = 2; i < N + 1; ++i) lgx_table[i] = lgx_table[i >> 1] + 1;
        lgN = lgx_table[N] + 1;
        d.assign(lgN, std::vector<S>(N, e()));
        d[0] = sequence;
        for (int h = 1; h < lgN; ++h) {
            for (int i = 0; i + (1 << h) <= N; ++i) {
                d[h][i] = op(d[h - 1][i], d[h - 1][i + (1 << (h - 1))]);
            }
        }
    }
    S prod(int l, int r) const { // [l, r), 0-indexed
        assert(l >= 0 and r <= N);
        if (l >= r) return e();
        int h = lgx_table[r - l];
        return op(d[h][l], d[h][r - (1 << h)]);
    }
};

Back to top page