Sparse Table
(datastructure/sparse_table.hpp)

• View this file on GitHub
• Last update: 2022-09-02 15:22:42+09:00
• Include: #include "datastructure/sparse_table.hpp"

概要

• 演算が冪等な半群に対する区間クエリを高速に処理する。

使い方

• SparseTable<S, op>(v): 半群 (S, op)、配列 v で初期化する。op は冪等な演算である必要がある($\min / \max$, $\gcd / \mathrm{lcm}$, $\mathrm{and} / \mathrm{or}$ など)。
• prod(l, r): $\mathrm{op} (\mathrm{op} (\cdots \mathrm{op} (\mathrm{v}{l}, \mathrm{v}{l+1}),\cdots ), \mathrm{v}_{r-1})$ を求める。

計算量

• 構築: $\mathcal O(N \log N)$
• クエリ: $\mathcal O(1)$

Verified with

• test/library-checker/staticrmq.test.cpp

Code

#pragma once
#include <cassert>
#include <vector>
template <class S, S (*op)(S, S)>
struct SparseTable {
public:
    SparseTable() {
    }
    SparseTable(const std::vector<S>& v)
        : _n(int(v.size())), d(_n), ceil_log2(_n + 1) {
        ceil_log2[0] = 0;
        ceil_log2[1] = 0;
        for (int i = 2; i <= _n; i++) ceil_log2[i] = ceil_log2[i >> 1] + 1;
        for (int i = 0; i < _n; i++) {
            d[i].resize(ceil_log2[_n] + 1);
            d[i][0] = v[i];
        }
        for (int b = 0; b < ceil_log2[_n]; b++) {
            for (int i = 0; i < _n; i++) {
                if (i + (1 << (b + 1)) > _n) break;
                d[i][b + 1] = op(d[i][b], d[i + (1 << b)][b]);
            }
        }
    }
    S prod(int l, int r) {
        assert(r - l > 0);
        int b = ceil_log2[r - l];
        return op(d[l][b], d[r - (1 << b)][b]);
    }

private:
    int _n;
    std::vector<std::vector<S>> d;
    std::vector<int> ceil_log2;
};

#line 2 "datastructure/sparse_table.hpp"
#include <cassert>
#include <vector>
template <class S, S (*op)(S, S)>
struct SparseTable {
public:
    SparseTable() {
    }
    SparseTable(const std::vector<S>& v)
        : _n(int(v.size())), d(_n), ceil_log2(_n + 1) {
        ceil_log2[0] = 0;
        ceil_log2[1] = 0;
        for (int i = 2; i <= _n; i++) ceil_log2[i] = ceil_log2[i >> 1] + 1;
        for (int i = 0; i < _n; i++) {
            d[i].resize(ceil_log2[_n] + 1);
            d[i][0] = v[i];
        }
        for (int b = 0; b < ceil_log2[_n]; b++) {
            for (int i = 0; i < _n; i++) {
                if (i + (1 << (b + 1)) > _n) break;
                d[i][b + 1] = op(d[i][b], d[i + (1 << b)][b]);
            }
        }
    }
    S prod(int l, int r) {
        assert(r - l > 0);
        int b = ceil_log2[r - l];
        return op(d[l][b], d[r - (1 << b)][b]);
    }

private:
    int _n;
    std::vector<std::vector<S>> d;
    std::vector<int> ceil_log2;
};

Back to top page