セグメント木
配列を更新したり区間でまとめて計算したりするやつ（ざっくり）
配列の長さ$ N とする
セグメント木(基本)
一点更新・区間和
update(i, x) : $ a_i を$ x で更新 $ O(\log N)
fold(l, r) : 区間$ [l,r) についての計算結果を得る $ O(\log N)
実装
長さ2Nの配列を用意して、
code:キホン
| 1 |
| 2 | 3 |
| 4 | 5 | 6 | 7 |
|8|9|a|b|c|d|e|f|
という感じで計算結果を入れておく。
元の配列は[N:2N]に入る
高さがだいたい$ \log N
update(i, x)
更新したい枠の上だけを再計算する
code:update
|###############|
| 2 |#######|
| 4 | 5 |###| 7 |
|8|9|a|b|c|#|e|f|
^ ここを更新したとき、###を再計算
各高さで更新されるのは1枠だけなので$ O(\log N)
fold(l, r)
できる限り高いところの計算結果を使っていく
code:update
| 1 |
| 2 | 3 |
| 4 |###|###| 7 |
|8|#|a|b|c|d|#|f|
~~~~~~~~~~~ ここを計算するとき、###を使う
各高さで使われるのは多くて2枠だけなので$ O(\log N)
乗る構造
モノイドならOK。隣同士以外が計算できなくても行けるので、圏と呼ばれる構造になるらしい参考 遅延セグメント木
区間更新・区間和
update(l, r, x) : 区間$ [l,r) の値を$ x で更新 $ O(\log N)
fold(l, r) : 区間$ [l,r) についての計算結果を得る $ O(\log N)
PAST上級本に詳しく載ってるので読みましょう
実装
長さ2Nの配列を用意してガチャガチャするのは同じ。
「あとで下を更新するのに使うデータ」:= 遅延データも持たせる
乗る構造
色々な解釈があるけど、ACLのドキュメントにある遅延データを$ S \rightarrow Sの関数とする解釈がわかりやすいカモ 値全体を$ S 、遅延データ全体を$ F 、$ F の単位元を$ \text{id} としたとき、3つの演算
$ \cdot \colon S \cdot S \rightarrow S (値同士の計算)
$ \times \colon F \times F \rightarrow F (遅延データの合成)
$ * \colon S * F \rightarrow S (遅延データを値に反映)
があって、
$ (S, \cdot) と$ (F, \times) がモノイド
$ \forall x \in S で$ x * \text{id} = x(恒等写像が存在する)
$ \forall x \in S, \forall f, g \in F で$ (x * f) * g = x * (f \times g) (合成写像で考えてもいい)
$ \forall x, y \in S, \forall f \in F で$ (x \cdot y) * f = x * f \cdot y * f (値同士の計算を後回しにしてもいい)
双対セグメント木
区間更新・一点取得
参考