DynamicLazySegmentTree
クラス · 動的遅延評価セグメント木
template <class S, class F>
requires monoid<S> && monoid<F> && acts_on<F, typename S::value_type>
struct DynamicLazySegmentTree;
概要
動的遅延評価セグメント木
テンプレートパラメータ
| 名前 | 説明 |
|---|---|
S |
データのモノイド |
F |
作用素モノイド（op が作用素の合成、f が値への作用） |
計算量
- 点更新・区間作用・区間積は領域長を $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)$ |
apply |
半開区間[a,b)にfを作用する | $O(\log n)$ |
all_prod |
全要素の積を返す | $O(1)$ |
prod |
半開区間[a,b)の積を返す | $O(\log n)$ |
演算子
| 名前 | 説明 | 計算量 |
|---|---|---|
operator[] |
k番目の値を返す | $O(\log n)$ |