むずいけど、まずは単純な「整数と区間MIN」などから実装していくと慣れてくる。
一口に遅延評価セグメント木といっても実装には自由度がある。
区間MINならこっちの方が書きやすいけど区間和ならこっち、みたいな細かな実装の違いがあり、各解説サイトではどういう前提を敷いているのか、注意しないといけない。
再帰の方がわかりやすいが、特にPythonなどインタプリタ言語では非再帰の方が高速。
dataを集約値の配列、lazyを遅延評価用の配列とする。
同じindexのdataの値に、lazyが反映済みの実装と、まだ反映させてない実装がある。
別に他の部分の実装によって何とでも変わりうるが、一般的には以下みたいな違いがある。
ちゃんとは比較していないが、よほど取得クエリより更新クエリの方が多いことが事前にわかってない限り、反映させておく実装の方がいいかな。
たとえば区間和で、ある $i$ を含む区間に対して「3足され、5足され、7足され」という情報が、$i$ の頭上の様々なノードに貯まっていく。
|---------- 7 ----------| |---- 5 ----|-----------| [2,4) に 3 |-----|- 3 -|-----|-----| [0,4) に 5 |--|--|--|--|--|--|--|--| [0,8) に 7 が足された 0 1 2 3 4 5 6 7
ここから実際に、たとえば $i=3$ の値が今いくつなのかを求める際には、上から遅延評価分を押し込むように反映させていく。
|-----------------------| |--- 12 ----|---- 7 ----| 7を下ろす |-----|- 3 -|-----|-----| |--|--|--|--|--|--|--|--| |-----------------------| |-----------|---- 7 ----| 12を下ろす |-12--|-15 -|-----|-----| |--|--|--|--|--|--|--|--| |-----------------------| |-----------|---- 7 ----| 15を下ろす |-12--|-----|-----|-----| |--|--|15|15|--|--|--|--|
この $3,5,7$ といった作用素を合成（今回は足し算）するにあたり、$3+5+7$ でなく $3+7+5$ などと順番を入れ替えても正しく求まるよ、というのが「可換」。
遅延評価という名の通り、区間にまとめて足し込んだ作用素は、いつかは下に反映させなければならない （まぁクエリが来なければしなくていいけど）。 その際、作用素が可換だとサボれる部分がある。
ここで、$F$ が可換なら、更新前の評価（★）を省け、若干の高速化に繋がる。
一方、非可換なら省けず、先に作用した分を評価しきってから更新を行う必要がある。
遅延データ |-----------------------| |-----3-----|-----------| [2,3) に 1 |-----|--2--|-----|-----| [2,4) に 2 |--|--|-1|--|--|--|--|--| [0,4) に 3 がこの順で足された 0 1 2 3 4 5 6 7 ■さらに [2,4) に 4 を足したい 可換の場合 |-----------------------| いきなり足してしまってOK。 |-----3-----|-----------| 意味合いとしては 1+(2+4)+3 となり、 |-----|--6--|-----|-----| 実際に作用させた順とは異なっているが、 |--|--|-1|--|--|--|--|--| 可換なので問題なし。 非可換の場合（非可換で単純な例が思いつかないのでここでは足し算で説明） |-----------------------| |-----------|-----------| 更新前に3を下ろして合成してから... |--3--|--5--|-----|-----| |--|--|-1|--|--|--|--|--| |-----------------------| |-----------|-----------| [2,4) に 4 を足す。 |--3--|--9--|-----|-----| これで意味合いとしては 1+(2+3+4) となり、 |--|--|-1|--|--|--|--|--| 実際に作用させた順と一致している。 0 1 2 3 4 5 6 7
整数の足し算、かけ算、XOR、MIN、MAX、GCD、LCMなどメジャーどころは可換。
行列の積などは非可換。
解説サイトでは注意してどちらを前提としているのか見る必要がある。
これは遅延セグ木に限らず普通のセグメント木でも注意を要するところだが、更新が既存の値を使うのかどうかで実装が変わってくる。
上書きの場合、少しテクニカルな書き方が必要となる。
作用素 $F$ がどうなるか考える。
その上で、mappingとcompositionは、以下のようになる。
S mapping(F f, S s): fが上書きフラグFalseならsをそのまま返し、それ以外ならfを反映させた値を返すF composition(F f, F g): 作用順はg→fとする。fが上書きフラグFalseならg、それ以外ならfを返す区間和を管理するセグメント木で、$[0,10)$ に一律 $2$ を加算したとき、区間 $[0,8)$、$[8,10)$ を表すノードの値はそれぞれいくつ増えるか。 当然、「作用させる値×区間長」なので $16, 4$ となる。
作用素が同じ $2$ でも区間長によってdataに反映する値が変わってくるような演算の場合、区間長をどう取得していつ反映させるかで複数の実装がある。
dataには最終的に反映させた値が必要として、
$F$ が整数とは限らない汎用的な実装にするには、 前者の方法では「$F$ を整数倍する処理」や「$F$ を半分にする処理」を定義する必要があるので、後者に分がある。
作用素を決める段階で、「区間全体に作用する集約値を計算しやすい」かつ「子に伝播させやすい」情報が何かを考えて決めるとよい。
だが、その中でも区間長をどこから取得するかについて複数ある。
また、MIN,MAXなどは区間長が必要ないので、汎用性のない（たとえばMINに決め打った）実装ではわざわざ考慮していないことも多い。考慮すると定数倍遅くなるし。
このあたりの方針が、問題によってもどの方法がいいか変わってくることもあるのか、割と統一されてない。
速度よりカスタマイズ性優先した、各関数を外部注入する形。
非再帰、作用素は非可換でも可、区間長はmapping時に反映（第3引数に区間長を入れる）。
型が2種類出てきてややこしいので、タイプヒンティングをしっかり目に。（実行上は意味ないが、IDEが対応してれば警告が出る）