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