概要
作用が可換なとき、作用の伝搬をしない遅延セグ木の実装のアイデアを紹介します。
（よく知られている内容ですが、意外とまとまった記事が見つからないので書きました）。
遅延セグ木の実装は AC(AtCoder) Library を基準とします。
また、遅延している作用をlazy, 遅延が反映済みの値を dataと呼ぶことにします。
区間作用
上図のような赤い区間への作用を考えます。
通常の遅延セグ木では次のステップで区間作用を実現します。
- Step 1:
lazy側の遅延を解消する（黄色の部分） - Step 2:
lazy,data両方に作用を反映させる（赤色の部分） - Step 3:
data側の不整合を解消する（水色の部分）
一方、作用が可換なときは次のステップで区間作用が実現できます。
- Step 1': 何もしない
- Step 2':
lazy,data両方に作用を反映させる（赤色の部分） - Step 3':
data側の不整合を解消する（水色の部分）
ただし Step 3' で不整合を解消する際は、黄色の部分にある遅延を反映させるのを忘れないようにしましょう。
通常の遅延セグ木の実装が理解できていれば、こちらの実装は容易いでしょう。
なおこの節の内容は、双対セグ木（lazy側だけを持つ、区間作用1点取得のデータ構造）にも当然適用できます。
区間取得
上図のような赤い区間の区間和を取得することを考えます。
通常の遅延セグ木では次のステップで区間取得を実現します。
- Step 1:
lazy側の遅延を解消する（黄色の部分） - Step 2:
data側で区間和をとる（赤色の部分）
一方、作用が可換なときは次のステップで区間作用が実現できます。
- Step 1': 何もしない
- Step 2':
data側を上に登り、必要な（赤色の）区間との和をとりながら遅延（黄色）を反映させる
区間取得クエリが再帰で実装されている場合は、これらは素直に実装できます（なのでむしろ平衡二分木とか領域木とかだと自然に使えるかも）
非再帰での実装は少し複雑になる気がします。
区間の L 側を縮めていくことを考えます（R側も同様です）。
段を上に移動していくとき、はじめてL>>1と(L+1)>>1の値が異なるときに区間が採用されます。
それ以降は、初期値の L の真上方向のセルにある遅延した作用を常に適用することになります。
二分探索
二分探索の際は、まずセグ木の段を上がり、その後段を降りていきます。
上がる部分では、遅延している作用の累積和を計算して、それを逆順に見ます。
降りる部分では、作用の累積和の途中から、順に必要な作用を反映させればよいでしょう。
区間作用の取り消しへの応用
伝搬の有無は単なる計算量削減以上に意味があります。
伝搬が行われると、「区間 X へ作用した」という情報が失われてしまいます。たとえば「区間 $[0,4)$ へ作用して、伝搬する」と「区間 $[0,2)$ と$[2,4)$ にそれぞれ作用する」が区別できません。
たとえば「区間作用の取り消し」など「区間 X へ作用した」という情報が重要な場合、伝搬をしないことでその情報を失わずに済み、効率のよいアルゴリズムを設計できる可能性があります。
たとえば次のような状況で区間作用の取り消しが行われます。
- 過去の改変、特に削除が行われる設定 (retroactive 系の問題）
- 長方形の平面走査（挿入した区間と同じ区間が削除される）