lazy_segtree/

Details

Last Change: 2020-10-06 02:19:48.

かなりわかりやすかった。自分的に重要ポイントだと思ったところを抽出する。

遅延セグ木というデータ構造上の文脈では、 lazy -> data と伝搬させることに相当する。

数式を借りて抽象的に議論すると、 f を x に作用させる関数とか f(x) と解釈できる。特に、恒等写像については id(x) == x 。

mapping には重要な制約がある。 それは、「すでに取得演算 prod してしまった値に対して作用させてOK」ということ。

例えば、区間Minなら min(f(a0), f(a1), f(a2), f(a3)) == f(min(a0, a1, a2, a3)) であるため、この条件はクリアする。

遅延セグ木というデータ構造上の文脈では、 lazy にさらに作用を「貯める」イメージ（多分）。

数式を借りて抽象的に議論すると、作用 g の 「後に」作用 f を作用させる とか f(g(x)) に相当するものを返す、と言える。

※ブログのここのみを意識しておけば問題ないのかも。

結局の所 op, mapping, composition を適切に定義できるかどうか？という点に尽きる。 単位元や恒等写像はどうとでもなる（とのこと）。

op: 結合法則を満たすか？
mapping: 操作を「すべての」ノードが持つ data に「同じ」計算式で作用させることができるか？
- 迷ったら op が Min の例を思い浮かべるのが良い。
composition: 複数の操作を連続して行うという操作（合成写像）を、あたかも「1回の操作であるかのように扱って」 lazy に持たせることができること。

※（おそらく）恒等写像の定義の仕方によって、 mapping, composition は影響を受けるのが普通。

個人的にはアルメリアさんの解説のほうが好みだったが、「条件4, 5の更新クエリに対する条件」はコンパクトで良いと感じた。

data[i] の更新規則が data[j] (i != j) の値に依存しない。
[l, r) に対する2つの更新クエリ g, f を考える。 g を適用した後に f を適用することは、別の「同種の」更新クエリ h を1回適用することと等価である。

※特に上の条件（4の条件）の方が大事かも。

op したあとの S の要素に対する写像の適用にあたっての調整は、 mapping が引き受けてくれる。
- なんか op の方にも手を加えなければいけないのかも？と思いたくなる時がある。
  - もしかしたら、問題に寄っては op にも手を加えなければ行けないものもあるかもしれない。
  - というか、モノイドに区間幅をもたせるようなものは、すでに op にも影響が出ているのかもしれない。
とにかく公式のドキュメントの記述が素晴らしくまとまっているので、問題を解くときは開いておいたほうがいい。
- これに尽きる気がする。