SegmentTree2D
クラス · 二次元セグメント木
template <monoid M>
struct SegmentTree2D;
概要
二次元セグメント木
計算量
- 点更新・矩形積は $O(\log h\log w)$
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
h行w列の空の木を構築する | $O(1)$ |
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
at |
座標(x,y)の値を返す | $O(\log h\log w)$ |
get |
座標(x,y)の値を返す | $O(\log h\log w)$ |
set |
座標(x,y)をvalへ変更する | $O(\log h\log w)$ |
reset |
座標(x,y)を単位元へ戻す | $O(\log h\log w)$ |
all_prod |
全要素の積を返す | $O(1)$ |
prod |
行[xl,xr)・列[yl,yr)の矩形積を返す | $O(\log h\log w)$ |
メンバ型
| 名前 | 説明 | 計算量 |
|---|---|---|
node_ptr |
内部ノードへのpointer型 | 型エイリアスで実行時計算量はない |