Sparse-Table (src/DataStructure/SparseTable.hpp)

View this file on GitHub
View document part on GitHub
Last update: 2024-09-20 12:04:43+09:00
Include: #include "src/DataStructure/SparseTable.hpp"

結合則と冪等則を満たす二項演算子を渡して区間のまとめあげを高速に行うデータ構造.
冪等則を要求する代わりに disjoint-sparse-table より定数倍が良い.

メンバ関数

名前	概要	計算量
`SparseTable(v,f)`	コンストラクタ. 配列 `v` と2変数引数の関数 `f` 渡す.	以下配列のサイズを $n$ とする. $O(n\log n)$
`prod(l,r)`	半開区間$\lbrack l,r)$ について `f` でまとめあげた値を返す.	$O(1)$

Verified with

Code

#pragma once
#include <vector>
template <class T, class F> class SparseTable {
 std::vector<std::vector<T>> dat;
 F f;
public:
 SparseTable() {}
 SparseTable(const std::vector<T> &v, const F &f): f(f) {
  int n= v.size(), log= n > 1 ? 31 - __builtin_clz(n - 1) : 0;
  dat.resize(log + 1), dat[0].assign(v.begin(), v.end());
  for (int i= 0, I= 1, j; i < log; ++i, I<<= 1)
   for (dat[i + 1].resize(j= dat[i].size() - I); j--;) dat[i + 1][j]= f(dat[i][j], dat[i][j + I]);
 }
 // [l, r)
 T prod(int l, int r) const {
  if (r == l + 1) return dat[0][l];
  int k= 31 - __builtin_clz(r - l - 1);
  return f(dat[k][l], dat[k][r - (1 << k)]);
 }
};

#line 2 "src/DataStructure/SparseTable.hpp"
#include <vector>
template <class T, class F> class SparseTable {
 std::vector<std::vector<T>> dat;
 F f;
public:
 SparseTable() {}
 SparseTable(const std::vector<T> &v, const F &f): f(f) {
  int n= v.size(), log= n > 1 ? 31 - __builtin_clz(n - 1) : 0;
  dat.resize(log + 1), dat[0].assign(v.begin(), v.end());
  for (int i= 0, I= 1, j; i < log; ++i, I<<= 1)
   for (dat[i + 1].resize(j= dat[i].size() - I); j--;) dat[i + 1][j]= f(dat[i][j], dat[i][j + I]);
 }
 // [l, r)
 T prod(int l, int r) const {
  if (r == l + 1) return dat[0][l];
  int k= 31 - __builtin_clz(r - l - 1);
  return f(dat[k][l], dat[k][r - (1 << k)]);
 }
};