遅延セグ木を思いつく流れを追う用の記事

敬遠されがちみたいな印象がある^[要出典]*1ので、書いてみます。

問題

以下のような問題設定を考えます。

集合 \(S\), \(T\) と、それに関する演算 \(\circ: S\times S\to S\), \(\star: S\times T\to S\) があります。 変数 \(a_1, a_2\in S\) があり、初期値が与えられます。 あなたは、変数 \(a'_1, a'_2, a' \in S\) と \(x' \in T\) のみ読み書きできます。 以下のクエリを処理してください。

• 単一クエリ
  • \(x\) が与えられ、\(a_1 \gets a_1 \star x\) で更新する。
  • \(x\) が与えられ、\(a_2 \gets a_2 \star x\) で更新する。
  • \(a_1\) を答える。
  • \(a_2\) を答える。
• 複数クエリ
  • \(x\) が与えられ、\(a_1 \gets a_1 \star x\) および \(a_2 \gets a_2 \star x\) で更新する。
  • \(a_1 \circ a_2\) を答える。

ただし、複数クエリが与えられたときは、\(a'\) と \(x'\) にのみアクセスできるとします。

単一クエリにおいては、アクセスは自由とします。 たとえば、\(a_1\) を答えるときに \(a'_2\) や \(x'\) を更新してもよいとします。

ここでは \(\circ\), \(\star\) が持つ性質には特に触れていません。 これ以降で問題を解きながら「こういう性質があれば解けるな〜」というのを探していく流れになります。

記号が苦手な人は、\(S\), \(T\) が int、\(\circ\) が min、\(\star\) が + のような例をイメージするといいかもしれません*2。

観察 1

まず、\(a_1 \circ a_2\) を答える際に \(a'_1\), \(a'_2\) に触れられないので、\(a' = a_1 \circ a_2\) にしておきたいな〜という気持ちになります。

それから、更新する際にもそれらに触れられないので、\( (a_1 \star x) \circ (a_2 \star x) = (a_1\circ a_2)\star x\) みたいな性質が成り立ってほしいな〜となります。前者と合わせて \(a \gets a\circ x\) と更新してよくなるためです。

さらに、このとき、実際には \(a_1 = a'_1 \star x\) のように乖離が生じるため、「\(a'_1\gets a'_1 \star x\) する必要がある」というのを覚えておく必要があります。これを \(x'\) で管理しておきます。

また、連続して複数更新クエリ（値はそれぞれ \(x\), \(y\) とする）が来ると、\(T\) に関する変数は一つしか持っていないので困ります。 そこで、ある演算 \(\ast: T\times T\to T\) があり、\(x'\gets x\ast y\) としてもよいという性質があるとうれしいです。 すなわち、一回ずつ更新する \( (a'_1\star x)\star y\) と、まとめて更新する \(a'_1 \star (x\ast y)\) が同じになってほしいです。 \(a'_2\) についても同様で、一般に \(S\) の要素全部についてそうであってほしいです。

欲しい性質まとめ

ここまでで欲しくなった性質は次の通りです。

• \( (a_1 \star x)\circ(a_2 \star x) = (a_1\circ a_2) \star x\)
• \( (a \star x)\star y = a \star (x\ast y)\) を満たす \(\ast: T\times T\to T\) が存在する

観察 2

上記の性質が成り立つとして、方針を詰めていきます。

以下の不変条件が成り立つように管理します。

• \(a_1 = a'_1 \star x'\)
• \(a_2 = a'_2 \star x'\)
• \(a' = a_1 \circ a_2\)

これらより、\(a' = (a'_1 \circ a'_2) \star x'\) が成り立っていることになります。

複数クエリに関しては、\(a'\) を答えるのと、\(a' \gets a'\star x\) および \(x' \gets x'\ast x\) で更新するだけなので、単一クエリについて考えます。

単一クエリでは、変数に自由にアクセスできるので、\(a'_1 = a_1\) が成り立つようにします。\(a'_1 \gets a'_1 \star x'\) です。\(a'_2\) についても同様です。 この際、不変条件から、\(a_1 = a_1 \star x'\) になってほしいので、そういう元 \(\mathrm{id}_T\) があって \(a_1 = a_1\star \mathrm{id}_T\) が成り立ってほしいです*3。これを使って \(x'\gets \mathrm{id}_T\) とします。

もう \(a'_1 = a_1\) になったので、出力クエリでは \(a'_1\) を答えればよいです。更新クエリにおいては、\(a'_1 \gets a'_1 \star x\) で更新し、\(a'\gets a'_1\circ a'_2\) と直しておきます。こちらも \(a'_2\) についても同様です。

\(a'_1 = a_1\) にすることを、\(a'_1\) の遅延を解消する (force) と呼ぶことにします*4。

本題

ここまで来れば、遅延セグ木は実質わかったと言えそうです。

前問で 2 つだけの要素 \(a_1, a_2\in S\) だったのを、4 つの要素 \(a_1, a_2, a_3, a_4\in S\) にしてみます。

           [ (a[1234], x[1234]) ]
 [ (a[12], x[12]) ]      [ (a[34], x[34]) ]
[ a[1] ]    [ a[2] ]    [ a[3] ]    [ a[4] ]

アクセスできる変数は、関連するノードの（真の (proper)）祖先の直接の子のみとします。たとえば、a[3] に関するクエリが来た場合は a[3] a[4] a[12] x[12] a[34] x[34] a[1234] x[1234]、a[12] に関するクエリが来た場合は a[12] x[12] a[34] x[34] a[1234] x[1234]、a[1234] に関するクエリが来た場合は a[1234] x[1234] です。

こんな感じでイメージすると、前問の

    [ (a, x) ]         [ (a[12], x[12]) ]
[ a[1] ]  [ a[2] ] =~ [ a[1] ]    [ a[2] ]

    [ (a, x) ]         [ (a[34], x[34]) ]
[ a[1] ]  [ a[2] ] =~ [ a[3] ]    [ a[4] ]

    [ (a, x) ]                [ (a[1234], x[1234]) ]
[ a[1] ]  [ a[2] ] =~ [ (a[12], x[12]) ]  [ (a[34], x[34]) ]

との対応づけがわかりそうです。最後（木で言うと根）に関してのみ、子が \(x\) を持っているのが違いますが、\(x\) はそのまま子に渡してよい (\( (a_1\circ a_2)\star x = (a_1\star x)\circ(a_2\star x)\) から従う) ので、\(a'_{\text{child}}\) の更新の際に、加えて \(x'_{\text{child}} \gets x'_{\text{child}} \ast x'_{\text{parent}}\) で更新すればよいです。

\(a_1\circ\dots\circ a_4\) を求めるクエリにおいては、（適宜 force して更新してから）ふつうのセグ木のようにまとめていくので、\( (S, \circ)\) はモノイドになっていてほしいです。

また、\(T\) に関しても、\(x_1 \ast x_2\) で更新されてから \(x_3\) で更新された場合と、\(x_1\) で更新されてから \(x_2\ast x_3\) で更新された場合とで値が変わると困るので、\( (T, \ast)\) もモノイドになってほしいです。

これらより、必要なノードにアクセスするだけでクエリ処理できることになりました。 もちろん、4 つではなくて一般に \(n\) 個について適用でき、必要なノードは \(O(\log(n))\) 個なので、\(O(\log(n))\) 時間で処理できます。

成り立ってほしい性質

• \( (S, \circ)\) はモノイドを成す*5
• \( (a_1 \star x)\circ(a_2 \star x) = (a_1\circ a_2) \star x\)
• \( (a \star x)\star y = a \star (x\ast y)\) を満たす \(\ast: T\times T\to T\) が存在する
• \( (T, \ast)\) はモノイドを成し、単位元が \(\mathrm{id}_T\)
• \(a \star \mathrm{id}_T = a\)

その他

遅延セグ木で問題を解く際には、\(\ast\) を高速に計算できるように考えたり、\(\star\) に関する性質が成り立つように \(S\) や \(T\) を工夫することが基本になりそうです。

初心者が勘違いしがちですが、区間 \(\star\) 更新クエリと区間 \(\circ\)-fold クエリの内容によって、\(S\) が持つべき情報（あるいは定義の可否）が変わります。区間加算クエリと区間 \(\min\) クエリが可能だからといって、区間加算クエリと区間任意-fold クエリができたり、区間任意更新クエリと区間 \(\min\) クエリができたりするとは言えません。

また、区間加算クエリを区間和クエリと一緒にやるためには、\(S\) に要素数も持たせる必要もあります*6。int とかのペアにするみたいな感じですね。

参考文献

qiita.com

opt-cp.com

ACL のドキュメント + Appendix も読むとよいです。

おわりねこ

遅延セグ木とか全方位木 DP とかのように、うまいことやっておいて汎用的に使えるライブラリを作る・考えるのは、よい勉強になると思います。遅延セグ木は ACL にもありますが、実装の考え方をわかっていると、どのような代数的構造が扱えるのかを丸暗記せずに済むのでよさそうです。

抽象化ライブラリの作成はコンテストで問題を解くよりも得てして大変なことが多いです。

競技プログラミングの勉強法としては不向きかもしれませんが、アルゴリズムやプログラミング言語に対する理解を深める方法の 1 つとしてはありだと個人的に思っています。

atcoder.jp

競プロで出てくる抽象化ライブラリ、大抵がモノイド (+ なんか) が乗ってがち*7なので、競プロ er モノイドとは仲いいがち。BIT はモノイドではないけど。

ダブリングとかもモノイドが乗ってそう。木や functional graph 上でやるやつとか。

WM とか CHT とか slope trick とかは抽象化したりしにくそう。\(\langle O(n), O(1)\rangle\) decremental neighbor query とかも整数モノだからつらそう。

WM + なんかで重みつき矩形和みたいなのは可換モノイドが乗る？ Union-find にポテンシャルをつけるやつ（最近あんまり見ない）には群が乗る？

文字列系のやつを除けば、初等的な競プロで出てくるデータ構造ってこのくらいしかない気がするね。

rsk0315.hatenablog.com

CHT も知りたい人は読んでね。

*1:別に個人の感想なんだから出典とかいらなくない？

*2:実際には int は + について閉じていないですが、そういうのは一旦無視です。

*3:\(\star\) しても \(S\) の値を変えないような元。\(\mathrm{id}_T\) は、\( (T, \ast)\) についても単位元になりそうです。実際にはなるとは限らない場合もあるかも。そんなことないかも。

*4:関数型言語とかの遅延評価の文脈でそういう用語が使われるみたいなので。遅延をやめて、評価することを強制するみたいな意味合いかも。

*5:モノイドをなすがすきなす

*6:要素数に関しては、こうした考察から必要になってくるものなので、モノイド側が計算するのが自然で、セグ木側で渡してあげるのは不自然かなという気持ちがあります。区間代入クエリと区間ロリハクエリとかでは、要素数ではなく b^要素数 が必要になったりするので。

*7:foldable queue (SWAG)、tree catamorphism (全方位木 DP)、とか。