DisjointSparseTable
(src/data_structure/disjoint_sparse_table.hpp)

View this file on GitHub
Last update: 2025-02-05 15:45:56+09:00
Include: #include "src/data_structure/disjoint_sparse_table.hpp"

DisjointSparseTable

モノイド，つまり

結合則: $(a \cdot b) \cdot c = a \cdot (b \cdot c)$ for all $a, b, c \in S$
単位元の存在: $a \cdot e = e \cdot a = a$ for all $a \in S$

を満たす代数構造に対し使用できるデータ構造です．

長さ $N$ の $S$ の配列に対し，

区間の要素の総積の取得

を $O(1)$ で行うことができます．

ただし，これは二項演算 op と単位元取得 e が定数時間で動くと仮定したときの計算量です．
これらが $O(f(n))$ かかる場合は，すべての計算量が $O(f(n))$ 倍となります．

また，要素を更新することはできません．

コンストラクタ

DisjointSparseTable<S, op, e> st(vector<S> v)

型 S
二項演算 S op(S a, S b)
単位元 S e()

を定義する必要があります．

例として，Range Minimum Queryなら，

int op(int a, int b) {
    return min(a, b);
}
int e() {
    return (int)1e9;
}
SparseTable<int, op, e> st(v);

のようになります．

長さ n = ssize(v) の数列 a を作ります．
v の内容が初期値となります．

計算量

$O(n \log n)$

prod

S st.prod(int l, int r)

op(a[l], a[l + 1], ..., a[r - 1]) を，モノイドの性質を満たしていると仮定して返します．
$l = r$ のときは e() を返します．

制約

$0 \leq l \leq r \leq n$

計算量

$O(1)$

Depends on

template (src/template/template.hpp)

Verified with

Code

#pragma once
#include "../template/template.hpp"
template <typename S, auto op, auto e>
struct DisjointSparseTable {
    DisjointSparseTable(const vector<S>& v)
        : n((int)v.size() + 2) {
        const int b = 32 - __builtin_clz(n - 1);
        table.assign(b, vector<S>(n, e()));
        for(int k = 1; k < b; ++k) {
            const int w = (1 << k);
            for(int i = w; i < n; i += w * 2) {
                for(int j = i - 1; j > i - w; --j) {
                    table[k][j - 1] = op(table[k][j], v[j - 1]);
                }
                const int m = min(i + w - 1, n - 1);
                for(int j = i; j < m; ++j) {
                    table[k][j + 1] = op(table[k][j], v[j - 1]);
                }
            }
        }
    }
    S prod(const int l, int r) const {
        assert(0 <= l and l <= r and r <= n);
        ++r;
        const auto& s = table[31 - __builtin_clz(l xor r)];
        return op(s[l], s[r]);
    }

   private:
    int n;
    vector<vector<S>> table;
};

#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/data_structure/disjoint_sparse_table.hpp"
template <typename S, auto op, auto e>
struct DisjointSparseTable {
    DisjointSparseTable(const vector<S>& v)
        : n((int)v.size() + 2) {
        const int b = 32 - __builtin_clz(n - 1);
        table.assign(b, vector<S>(n, e()));
        for(int k = 1; k < b; ++k) {
            const int w = (1 << k);
            for(int i = w; i < n; i += w * 2) {
                for(int j = i - 1; j > i - w; --j) {
                    table[k][j - 1] = op(table[k][j], v[j - 1]);
                }
                const int m = min(i + w - 1, n - 1);
                for(int j = i; j < m; ++j) {
                    table[k][j + 1] = op(table[k][j], v[j - 1]);
                }
            }
        }
    }
    S prod(const int l, int r) const {
        assert(0 <= l and l <= r and r <= n);
        ++r;
        const auto& s = table[31 - __builtin_clz(l xor r)];
        return op(s[l], s[r]);
    }

   private:
    int n;
    vector<vector<S>> table;
};

DisjointSparseTable (src/data_structure/disjoint_sparse_table.hpp)