【ACL】遅延セグメント木

セグメント木は前に備忘録書いてなんとなくわかった気になっていたが、
遅延セグ木は使い方よくわからんかった。

宣言しておくもの

• S：データの型。intとかなら不要。普通のセグ木と同じ。
• S op(S a, S b)：ノード間からどういう値を抽出するか。普通のセグ木と同じ。
• S e()：opに対しての単位元。普通のセグ木と同じ。
• F：値の更新（写像）の型。intを足すとかだったらint
• F mapping(F f, S x)：区間の値更新の関数。あるデータx（seg[i]とか）にfを作用させたときの関数？int足すならreturn x+f;
• F composition(F f, F g)：2つの写像f,gを、f・g・seg[i]と作用させたとき、f・gがどういう写像になるか。
• F id()：（疑似的な）恒等写像。

要素の更新が「ある値に変更する」だった場合。
mapping, composition, idをうまく定義してやる必要がある。
atcoder.jp

このサイトのおかげで理解できました。
AtCoder LibraryのLazy Segtreeの使い方 - ARMERIA