RangeTree
クラス · 領域木
template <class M, class T = int>
struct RangeTree;
概要
領域木
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
空の領域木を構築する | $O(1)$ |
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
add |
build前に使用する座標を登録する | 償却 $O(1)$ |
build |
登録した座標から領域木を構築する | 登録点数を $n$ として時間・空間ともに $O(n\log n)$ |
set |
登録点の値を設定する | $O(\log^2 n)$ |
prod |
半開矩形 $[x_l,x_r)\times[y_l,y_r)$ のモノイド積を返す | $O(\log^2 n)$ |
get |
登録点の値を返し、未登録なら単位元を返す | $O(\log n)$ |