指示された「区間更新 + 何かのクエリ」を遅延セグ木で解ける状況で、思考停止で遅延セグ木を貼って AC できる人に対するお気持ち表明ではないです。
「区間更新」の部分だけを見て「どうやら遅延セグ木というので解けるらしいが自分はよく知らない。だから AC できなさそう。ふて寝です」みたいな人向けの記事です。
もしかすると前者の人にも学びのある内容にはなっているかもしれません。
導入
（更新クエリではない方の）値を求めるクエリや、他の更新クエリによって、使うべきデータ構造は変わります。
たとえば、以下のような（ふざけた）問題を考えます。
サイズ $n$ の配列 $a = (0, 0, \dots, 0)$ が与えられる。 以下のクエリをたくさん処理せよ。
1$l$ $r$ $x$
- $a_l, a_{l+1}, \dots, a_{r-1}$ の値を $x$ で更新せよ。
2
- $a_0$ の値を出力せよ。
これであれば、$a_0$ の値さえ管理しておけばよいことがわかります。 ここまでふざけた状況ではなくても、ある状況においては遅延セグ木を使わずに処理できる場合があるので、その紹介です。
いろいろな状況
以下のような問題を考えます。
サイズ $n$ の配列 $a$ が与えられる。 以下のクエリをたくさん処理せよ。
1$l$ $r$
- $x = \max\,\{a_l, a_{l+1}, \dots, a_{r-1}\}$ とする。
- $x$ の値を出力せよ。
- さらに、$a_l, a_{l+1}, \dots, a_{r-1}$ を $x + 1$ で更新せよ。
これは、一般の「区間更新・区間最大値」よりも限定された状況です。この状況であれば、遅延セグ木なしでも処理することができます。
以下の解説に書いた手法により、BIT や普通のセグ木、あるいは平衡二分探索木（C++ における std::set や std::map）などを用いることで、$\angled{O(n), O(\log(n))}$ (amortized) で処理できます。
典型 90 の個別解説、一覧で見れないので若干見つかりにくそう。
あるいは、以下のようなクエリも（簡単な補助のデータ構造を持つことで）同じオーダーの計算量で処理できます。
サイズ $n$ の配列 $a$ が与えられる。 以下のクエリをたくさん処理せよ。
1$l$ $r$ $x$
- $a_l, a_{l+1}, \dots, a_{r-1}$ を $x$ で更新せよ。
2$i$
- $a_i$ を出力せよ。
3
- $a$ に含まれる値の種類数、すなわち集合 $\{a_i\mid 0\le i\lt n\}$ の大きさを出力せよ。
4$x$
- $a$ に含まれる $x$ の個数、すなわち集合 $\{i \mid a_i = x\}$ の大きさを出力せよ。
特に 3 4 は遅延セグ木で普通に処理するのは難しいと思います。
別のデータ構造
双対セグ木と呼ばれる亜種もあります。区間操作・添字取得をするデータ構造です。
注意
とはいえ、遅延セグ木は避け続けるほど難しいデータ構造ではないはず*1なので、適当なタイミングで学んでしまって、思考停止で貼れる問題は AC できるようにした方が得とも思います。
人によってわかりやすい記事は分かれると思いますが、えびちゃんのお気持ちを追う用の記事は以下です。一番最初に読む用の内容ではないかもしれませんが、他に参考になりそうな記事へのリンクも載っているので紹介します。合わなければ他のブログなどを漁るのもよいでしょう。
謝辞
一連の話は、こちらの記事がきっかけで思いついて書く流れになったので、お礼です。
おわり
ねこにゃんこ。
*1:初心者のうちに何が何でも勉強するのを強いる意図ではないです。挫折させたいわけではないので。
