DynamicSegmentTree
クラス · 動的セグメント木
template <monoid M>
struct DynamicSegmentTree;
概要
動的セグメント木
計算量
- 点更新・区間積は領域長を $n$ として $O(\log n)$
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
添字領域[0,n)の空の木を構築する | $O(1)$ |
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
at |
k番目の値を返す | $O(\log n)$ |
get |
k番目の値を返す | $O(\log n)$ |
set |
k番目をvalへ変更する | $O(\log n)$ |
reset |
k番目を単位元へ戻す | $O(\log n)$ |
all_prod |
全要素の積を返す | $O(1)$ |
prod |
半開区間[a,b)の積を返す | $O(\log n)$ |
演算子
| 名前 | 説明 | 計算量 |
|---|---|---|
operator[] |
k番目の値を返す | $O(\log n)$ |