disjoint_sparse_table
クラス · Disjoint Sparse Table
template <monoid M>
struct disjoint_sparse_table;
概要
Disjoint Sparse Table
計算量
- 構築は $O(n\log n)$、区間積は $O(1)$
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
列vから構築する | $O(n\log n)$ |
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
prod |
半開区間[l,r)の積を返す | $O(1)$ |