※2023/03/14 分類1の再評価のタイミングが誤ってたため，文章とコードを修正。
修正内容(クリックで展開)
「ノードk以降の情報に触れるとき」ではなく，正しくは「ノードkを見るとき」。区間更新ではノードkが範囲外でもその親がvalを参照するため，再評価する必要がある。よって厳密にはこの再評価のタイミングの理由は「親がlazyではなくvalを参照するから」であるが，分かりやすさ・覚えやすさを重視して分類法は変更していない。また，区間クエリでは範囲外のときに再評価を行う必要は無いが，行っても支障は無いので，区間更新にタイミングを合わせておく。
遅延セグ木の再評価のタイミングと必要性について疑問に思うことが度々あるのでまとめておく。
目次
例題
[典型90] 029 - Long Bricks (★5)
概要は，「幅 の地面に
から
までの細長いレンガを置く。
個目のレンガを置いたときの高さを出力せよ」というもの。テトリスみたいな感じ。
再評価が必要なタイミング
以下のコードは，区間の最大値を管理する遅延セグ木である。
この問題に限らず，再評価(lazyをvalに反映)が必要なタイミングは3箇所。
using ll = long long; struct LazySegTree{ int n; vector<ll> val; // val[i]:=ノードiが表す区間の高さの最大値 vector<ll> lazy; // lazy[i]:=ノードiで遅延している値 // コンストラクター LazySegTree(int _n){ n=1; while(n<_n) n*=2; val.resize(2*n-1,0); lazy.resize(2*n-1,0); } // 再評価 void eval(int k){ if(lazy[k]==0) return; val[k]=max(val[k],lazy[k]); if(k<n-1){ lazy[2*k+1]=max(lazy[2*k+1],lazy[k]); lazy[2*k+2]=max(lazy[2*k+2],lazy[k]); } lazy[k]=0; } // 区間更新 void update(int a,int b,ll x,int k=0,int l=0,int r=-1){ if(r<0) r=n; eval(k); // <- ココ(1) // 範囲外ならスルー if(r<=a || b<=l) return; if(a<=l && r<=b){ // 今見ている区間が完全に被覆しているのでlazyを更新 lazy[k]=max(lazy[k],x); // lazyをvalに反映 eval(k); // <- ココ(2) }else{ // 部分的に被覆しているので子を更新し、 update(a,b,x,2*k+1,l,(l+r)/2); update(a,b,x,2*k+2,(l+r)/2,r); // 子のvalを基に今見ている区間のvalを更新 // これ重要！ val[k]=max(val[2*k+1],val[2*k+2]); } } // 区間クエリ ll getMax(int a,int b,int k=0,int l=0,int r=-1){ if(r<0) r=n; eval(k); // <- ココ(3) // 範囲外ならスルー if(r<=a || b<=l) return 0; // 今見ている区間が完全に被覆していればvalを返す if(a<=l && r<=b) return val[k]; // そうでなければ子に渡して返ってきた値を基に返す return max(getMax(a,b,2*k+1,l,(l+r)/2), getMax(a,b,2*k+2,(l+r)/2,r)); } };
分類すると2種類である。
1. ノードk以降の情報に触れるときノードkを見るとき(1, 3)
2. 区間更新でのlazy更新直後(2)
そもそも遅延セグ木には「必要になるまで値の伝播を遅らせる」という着想のもと考案されたので，分類1は自然である。
問題は分類2である。必要になったときに再評価(lazyをvalに反映)するのだから，lazyを更新した直後のこの再評価は不必要な感じがする。本当にこの更新は必要だろうか？
考察
分類2の再評価があるときと無いときの出力を比べてみる。 例題の入力例1でも出力は異なってくるが，核心部分を抽出した次の入力例で考える。
4 2 2 3 1 2
画像のようにレンガを置いており，正解の出力は，
1 2
である。分類2の再評価のある(正しい)遅延セグ木では確かにこのように出力される。
しかし，分類2の再評価のない(誤った)遅延セグ木では次のように出力されてしまう。
1 1
2個目のレンガでの出力が誤っている。なぜだろうか？
順に処理を追いかけてみる。
個目のレンガに対する処理は次の順で行う(
l, rは0-indexed)。
1. getMax(l, r+1) でレンガを置く区間 の高さの最大値
を取得
2. update(l, r+1, M+1) でレンガを置き，区間 の高さを更新
3. 答えである を出力
getMaxやupdateでは分類1の再評価がその都度，適切なタイミングで行われるが，今回の入力例ではこの再評価による値の変化は無いので説明は省略する。
以降，画像の左側は正しい遅延セグ木，右側は分類2の再評価が無い誤った遅延セグ木である。また，各ノード内の数値は「(val) / (lazy)」を表す。
1個目のレンガ
処理1(最大値取得)：getMaxでどちらのセグ木も正しく を取得し，セグ木内の値の変化は無い。
処理2(高さの区間更新)：位置1, 2の高さを にしたいので，
updateで更新する。
まずはノード0が呼び出される。部分的に被覆しているので子を更新する。updateで左の子の区間更新を呼び出す。
ノード1が呼び出される。まだ部分的に被覆しているので子を更新。updateで左の子の区間更新を呼び出す。
ノード3が呼び出される。範囲外なので何もせず親に返す。
ノード1に戻る。updateで右の子の区間更新を呼び出す。
ノード4が呼び出される。完全に被覆しているのでlazyを更新する。
ここから二つのセグ木の処理に違いが生じる。正しい遅延セグ木では今見ているノード4のvalを更新してから親に返るが，誤った遅延セグ木はその処理をせずに親に返る。
ノード1に戻る。更新した子のvalを基にvalを更新する(コードに// これ重要！と記した箇所の処理)。そして親に返す。
ノード0に戻る。updateで右の子の区間更新を呼び出す。
ここから先の処理はこれまでと左右対称になっているので省略。再びノード0まで戻ったらvalを更新して，最終的には次のようになる。
処理3(答えの出力)： を出力。
2個目のレンガ
処理1(最大値取得)：getMaxで最大値を取得する。
まずはノード0が呼び出される。部分的に被覆しているので子に渡す。getMaxで左の子の区間クエリを呼び出す。
ノード1が呼び出される。完全に被覆しているのでvalを返す。
ノード0に戻る。getMaxで右の子の区間クエリを呼び出す。範囲外なので初期値0が返ってくる。
子からの返り値を基に最大値を返す。
これより，正しい遅延セグ木では が得られ，誤った遅延セグ木では
が得られた。
(処理2(高さの区間更新)：省略)
処理3(答えの出力)： を出力。正しい遅延セグ木では
，誤った遅延セグ木では
が出力される。
なぜ違いが生じたのか
分類2の再評価の有無が，区間更新におけるコードに// これ重要！と記した箇所の処理に大きく影響する。
この部分では子のvalを基にして自分のvalを更新している。だから，子のvalにはlazyを反映した最新の情報が保持されている必要がある。
直前の処理で子に潜っており，完全に被覆していた方の子はlazyを更新した。親が参照するのはlazyではなくvalなので，valを最新の情報にするために，子は再評価をする必要があるのだ。
これで親の方へ向かって再帰的に最新のvalが更新されていく。
もし分類2の再評価が無ければ，旧valで更新されていく。そこに区間クエリが来ると，完全に被覆している場合にはそのまま旧valで返してしまうため最終的な返り値が間違ってしまう。
まとめ
再評価(lazyをvalに反映)が必要なタイミングは3回あり，2種類に分類される。
