セグメント木とは
セグメント木（以下、セグ木）とは、二分木を作り、各ノード（頂点）に区間の情報を与えることで、区間クエリに 
で答えることができるデータ構造です。セグ木にはモノイドが乗ります。モノイドとは、以下の性質を満たす「集合Sと二項演算Fの組」です。
1. Fについて閉じている
Sの元と元でFをしたとき、その返り値がSの元である。
2. 結合則を満たす
例えば、Sの元s1、s2、s3について、F(F(s1, s2), s3) == F(s1, F(s2, s3))が成り立つ。
つまり、順番はそのままにしてどこから演算を行ってもよい。
3. 単位元がある
とあるSの元eが存在して、任意のSの元sに対してF(s, e)==sが成り立つ。
つまり、何回計算しても答えに影響を与えないような要素がある。
例えば、
足し算：0を足す
掛け算：1を掛ける
最小公倍数：1との最小公倍数を取る
最大公約数：0との最大公約数を取る
最小値の更新：取り得る一番大きい値よりも大きい値で更新する
最大値の更新：取り得る一番小さい値よりも小さい値で更新する
などです。
ちなみに、モノイドの集合Sについて、全部の元sに逆元s'がある（F(s, s') == e、eは単位元）とき、群と言います。
セグ木は、ノードが持つ要素の個数が2のべき乗になっています。区間クエリが欲しかったら、2のべき乗個ごとにまとまったものを二項演算Fでまとめるだけなので、 でこれを達成することができます。
普通のセグ木では一点更新・区間加算など、取得クエリのみ区間から得ることができます。もしくはimos法のようにして、区間加算・一点取得などもできますが、加算と取得の両方を区間に対して行うことはできません。それに対して、遅延セグメント木ではそれが可能です。
遅延セグ木を使ってみる
言語はC++、ライブラリはAtCoder Libraryを使います。ALPC（AtCoder Library Practice Contest）のK問題を解きます。
問題：K - Range Affine Range Sum
これは、区間の各要素にアフィン変換（a倍してb足す）をして、区間の和を取得するというクエリに答える問題です。遅延セグ木では、二項演算や単位元はいいとして、mappingとcompositionの設計が重要になってきます。また、単位元の写像バージョンである、恒等写像も要求されます。これは、何回適用しても要素が変わらない写像ということで、単位元と似ています。
では、実際のコードを見てください。
#include <atcoder/lazysegtree>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
struct S {
mint sum;
ll sz;
};
struct F {
mint b;
mint c;
};
vector<S> a(N);
rep(i, 0, N){
ll tmp;
cin >> tmp;
a[i] = {tmp, 1};
};
auto op = [](S s1, S s2){
return S{s1.sum+s2.sum, s1.sz+s2.sz};
};
auto ids = []{
return S{0, 1};
};
auto mapping = [](F f, S s){
return S{f.b*s.sum+f.c*s.sz, s.sz};
};
auto composition = [](F f1, F f2){
return F{f1.b*f2.b, f1.b*f2.c+f1.c};
};
auto idf = []{
return F{1, 0};
};
atcoder::lazy_segtree<S, op, ids, F, mapping, composition, idf> seg(a);
一部だけ切り抜きました。これを作ることができれば、あとはseg.apply(l, r, x)で[l, r)にxを作用させ、seg.prod(l, r)で区間クエリを取得して終わりです。この構築が難しかったりして、特にmappingとcompositionを見てください。また、元Sと作用素Fはどのようになっているかにも注目してください。ここで、SはDataであり、FはLazyです。
まず、遅延セグ木には8個の要素が必要です。
1. 元の型S
2. 二項演算op
3. 単位元ids（identity S）
4. 作用素の型F
5. 作用素と元から、元への写像mapping
6. 合成写像composition
7. 恒等写像idf（identity F）
8. 遅延セグ木のサイズ（単位元で初期化される）
（または、型Sの初期化配列）
1. 元の型S
区間加算をするとき、サイズlが分かると、それらすべてにxを足すので、全体の合計にはl倍のx足せばよいことが分かります。これがうれしいので、Sは構造体として、区間和と区間のサイズを持たせておきます。
2. 二項演算op
二つの型Sの元s1とs2が与えられたとき、これらを取得クエリとしてマージする際の計算です。今、区間和と区間のサイズを持っているので、それぞれ足せばよいです。
3. 単位元ids
元なので、型はSです。区間和は0を足しても変わらず、元としてサイズは1であるので、S{0, 1}が単位元となります。
4. 作用素の型F
b倍してc足すので、情報としてはbとcが欲しいです。これを構造体で持ちます。
5. 作用素と元から、元への写像mapping
難しいポイント1です。SにFを適用することを考えます。元SにF.b倍してF.cを足します。ここで、Sはすでにその区間全体が足されているので、そのS.sumを単にF.b倍すれば、全要素にF.b倍したことになります。また、S.szで区間のサイズが分かるので、S.sz倍してF.c足せば、全要素の分F.c足したことになり、これをS.sumに足せばよいです。サイズはLazyを適用しても変わらないので、そのままS.szを渡します。
6. 合成写像composition
難しいポイント2です。F f1とF f2について、それらの合成写像fを考えます。元sに対して、f = f1(f2(s))として合成します。これを展開すると、画像のようになり、最終的にf.b = f1.b×f2.b倍して、f.c = f1.b×f2.c+f1.cを足すことと同じとなり、それらをfとして返します。
7. 恒等写像idf
何回適用しても元が変わらない作用素Fなので、b = 1、c = 0とすると、1倍して0足すとなり、うまくいきます。
8. 遅延セグ木のサイズまたは、初期化配列
問題文で与えられている通りです。
これで遅延セグ木を完成させることができました。あとはクエリに素直に答えていけばよいです。
vector<S> ans;
rep(_, 0, Q){
ll t;
cin >> t;
if (t==0){
ll l, r, b, c;
cin >> l >> r >> b >> c;
seg.apply(l, r, F{b, c});
} else {
ll l, r;
cin >> l >> r;
ans.emplace_back(seg.prod(l, r));
}
}
提出：Submission #56201586 - AtCoder Library Practice Contest
これでこの問題は終わりです。しかし、何かに気づいた人はいませんか？（？）なんと、区間更新という演算には恒等写像が存在しません。何かの値に更新すると、元の値が変わってしまうため、影響を与えないような区間更新というものは存在しません。そのようなとき、恒等写像idfはどのように扱えばよいでしょうか。また、mappingやcompositionは、その恒等写像とどのように関わるでしょうか。
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
答え：擬似的な恒等写像として、取り得ない値にしておく。mappingとcompositionは、恒等写像と一致しているかどうかで場合分けをする。
以下はRange Update Range Minimumのコードの例です。
auto op = [](ll a, ll b){
return min(a, b);
};
auto ids = []{
return inf;
};
auto mapping = [](ll f, ll s){
if (f==-1){
return s;
} else {
return f;
}
};
auto composition = [](ll f1, ll f2){
if (f1==-1){
return f2;
} else {
return f1;
}
};
auto idf = []{
return -1LL;
};
Range Minimumなので、opは最小値、idsはinfとなっています。問題は作用素の方で、まず、取り得る値の範囲を[1, 10^9]などと仮定して、恒等写像は-1にしておきます。すると、mappingやcompositionに登場する作用素fは、-1のとき、何もしないとして扱うことができます。これを恒等写像とします。すると、あとは普通の遅延セグ木と同じように使うことができます。
compositionはcomposition(ll f1, ll f2)のとき、f2→f1の順に適用するので、f1が-1かどうかで場合分けすることに注意してください。
