linear_sparse_table
クラス · 線形 Sparse Table
template <monoid M>
struct linear_sparse_table;
概要
線形 Sparse Table
冪等なモノイドを仮定する。
計算量
- 構築は $O(n)$、区間積は $O(1)$
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
(1) 空のtableを構築する (2) 列vから構築する |
(1) $O(1)$ (2) $O(n)$ |
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
prod |
半開区間[l,r)の積を返す | $O(1)$ |
演算子
| 名前 | 説明 | 計算量 |
|---|---|---|
operator[] |
k番目の値を返す | $O(1)$ |
メンバの詳細
(constructor)
// (1)
linear_sparse_table() = default;
// (2)
linear_sparse_table(const std::vector<T> &v);
(1) 空のtableを構築する
- 計算量: $O(1)$
(2) 列vから構築する
- 計算量: $O(n)$