遅延セグメント木

この記事では遅延セグメント木の「気持ち」を説明します。
通常のセグメント木に関する知識を前提とします。
アルゴリズムの説明のみであり、実装については一切説明していません。
基本的には以下のサイトの記述を、自分好みにリライトしたものです。
beet-aizu.hatenablog.com

○遅延セグメント木とは

半群(M,⋅)$(M,\cdot )$
作用素モノイド({T:M→M},∘,id)$(\{T:M\to M\},\circ ,\mathrm{id})$の部分モノイドE$E$
E→E$E\to E$の写像f$f$
があり、次の(1)～(3)の条件を満たすとする。
(1) M$M$の演算、作用素の適用、作用素の合成はいずれもO(1)$O(1)$で行える
(2) fk(T)$f^k(T)$はT$T$にもk$k$にも依らずO(1)$O(1)$で計算できる
(3) ∀T∈E. ∀x,y∈M. (Tx)(Ty)=f(T)(xy)$\mathrm{\forall }T\in E.\mathrm{\forall }x,y\in M.(Tx)(Ty)=f(T)(xy)$ *1

このときM$M$上の長さN$N$の列{ai}$\{a_i\}$に対する2種類のクエリ(i)(ii)を遅延セグメント木によってO(logN)$O(\log N)$で処理することができる
(i)区間更新クエリ：区間I$I$と作用素T∈E$T\in E$が与えられ、全てのi∈I$i\in I$についてai$a_i$をTai$T{a}_i$に更新する
(ii)区間計算クエリ：区間I=[l,r)$I=[l,r)$が与えられ、alal−1…ar−1$a_l{a}_{l-1}\dots a_{r-1}$を求める

○実現する方法
通常のセグメント木では区間の積の情報を持っていたが、遅延セグメント木ではそれに加え、その区間全体に作用する作用素の情報を持つ。
これだけ。

○O(logN)$O(\log N)$でクエリが処理できることの確認
各nodeが長さを2k$2^k$の区間I$I$の情報を(x,T)$(x,T)$の形で持っているとする。
・区間更新クエリ
区間J$J$と作用素S$S$が与えられたとする。上から順に次のように各nodeを更新する。
(1)I⊂J$I\subset J$のとき
(x,T)$(x,T)$を(x,ST)$(x,ST)$に更新する
(2)I∩J=∅$I\cap J=\mathrm{\varnothing }$のとき
何もしない
(3)それ以外のとき
次の3つのことを行う
１．T$T$を子nodeに伝播する。即ち、子nodeが(x′,T′)$(x^{\prime },T^{\prime })$であるとき、これを(x′,TT′)$(x^{\prime },T{T}^{\prime })$に更新する
（↑これが肝となる遅延伝播）
２．子nodeを再帰的に更新する
３．子nodeの更新結果を元に自身のnodeが持つべき値y$y$を計算し、(y,id)$(y,\mathrm{id})$に更新する
以上の操作はO(logN)$O(\log N)$個のnodeをO(1)$O(1)$で更新するのでO(logN)$O(\log N)$となる。
・区間計算クエリ
区間J$J$が与えられたとする。上から順に次のように、各nodeを更新しながら値を計算する
(1)I⊂J$I\subset J$のとき
fk(T)(x)$f^k(T)(x)$を返す
(2)それ以外のとき
次の3つのことを行う
１．T$T$を子nodeに伝播する。即ち、子nodeが(x′,T′)$(x^{\prime },T^{\prime })$であるとき、これを(x′,TT′)$(x^{\prime },T{T}^{\prime })$に更新する
２．自身のnodeを、(fk(T)(x),id)$(f^k(T)(x),\mathrm{id})$に更新する
（更新クエリと違って値が変化しないので子を見る必要がない）
３．子nodeを再帰的に呼び出して値を計算したものを返す
以上の操作はO(logN)$O(\log N)$個のnodeをO(1)$O(1)$で更新/計算するのでO(logN)$O(\log N)$となる。

○自明な例
・区間加算クエリ＋区間和クエリ
M=(M,+),E={x↦x+k | k∈M},f(T)=T2$$\begin{gathered} M=(M,+), \\ E=\{x\mapsto x+k|k\in M\}, \\ f(T)=T^2 \end{gathered}$$
・区間加算クエリ＋区間maxクエリ
M=(M,max),E={x↦x+k | k∈M},f(T)=T$$\begin{gathered} M=(M,max), \\ E=\{x\mapsto x+k|k\in M\}, \\ f(T)=T \end{gathered}$$
・区間変更クエリ＋区間和クエリ
M=(M,+),E={x↦k | k∈M}∪{id},f(x↦k)=(x↦2k)$$\begin{gathered} M=(M,+), \\ E=\{x\mapsto k|k\in M\}\cup \{\mathrm{id}\}, \\ f(x\mapsto k)=(x\mapsto 2k) \end{gathered}$$
・区間変更クエリ＋区間maxクエリ
M=(M,max),E={x↦k | k∈M}∪{id},f(T)=T$$\begin{gathered} M=(M,max), \\ E=\{x\mapsto k|k\in M\}\cup \{\mathrm{id}\}, \\ f(T)=T \end{gathered}$$

○非自明な例１
Z$\mathbb{Z}$の数列{ai}$\{a_i\}$が与えられる。次のクエリに答えよ
(i)区間加算クエリ：区間I$I$と値k$k$が与えられ、全てのi∈I$i\in I$についてai$a_i$をai+k$a_i+k$に更新する
(ii)区間変更クエリ：区間I$I$と値k$k$が与えられ、全てのi∈I$i\in I$についてai$a_i$をk$k$に更新する
(iii)区間計算クエリ：区間I=[l,r)$I=[l,r)$が与えられ、al+al−1+…+ar−1$a_l+a_{l-1}+\dots +a_{r-1}$を求める

M=(Z,+),E={x↦x+k | k∈Z}∪{x↦k | k∈Z},f(x↦x+k)=(x↦x+2k),f(x↦k)=(x↦2k)$$\begin{gathered} M=(\mathbb{Z},+), \\ E=\{x\mapsto x+k|k\in \mathbb{Z}\}\cup \{x\mapsto k|k\in \mathbb{Z}\}, \\ f(x\mapsto x+k)=(x\mapsto x+2k), \\ f(x\mapsto k)=(x\mapsto 2k) \end{gathered}$$
（E$E$が写像の合成で閉じていることを確かめよ）

○非自明な例２
Z$\mathbb{Z}$の数列{ai}$\{a_i\}$と{bi}$\{b_i\}$が与えられる。次のクエリに答えよ
(i)区間更新クエリ：区間I$I$と値k$k$が与えられ、全てのi∈I$i\in I$についてai$a_i$をai+bik$a_i+b_{i}k$に更新する
(ii)区間計算クエリ：区間I=[l,r)$I=[l,r)$が与えられ、al+al−1+…+ar−1$a_l+a_{l-1}+\dots +a_{r-1}$を求める

M=(Z2,+),E={(a,b)↦(a+bk,b) | k∈Z},f(T)=T$$\begin{gathered} M=({\mathbb{Z}}^2,+), \\ E=\{(a,b)\mapsto (a+bk,b)|k\in \mathbb{Z}\}, \\ f(T)=T \end{gathered}$$

○非自明な例３
X={0,1,2,3,∞}$X=\{0,1,2,3,\mathrm{\infty }\}$とする。X$X$上の演算+$+$を
a+b={a+b∞(Z∪{∞}の元として) a+b≤3のとき(Z∪{∞}の元として) a+b≥4のとき$a+b=\{\begin{array}{ll}a+b& \text{(}\mathbb{Z}\cup \{\mathrm{\infty }\}\text{の元として) }a+b\le 3\text{のとき}\\ \mathrm{\infty }& \text{(}\mathbb{Z}\cup \{\mathrm{\infty }\}\text{の元として) }a+b\ge 4\text{のとき}\end{array}$
により定める。
X$X$の数列{ai}$\{a_i\}$が与えられる。次のクエリに答えよ
(i)区間更新クエリ：区間I$I$と値k$k$が与えられ、全てのi∈I$i\in I$についてai$a_i$をai+k$a_i+k$に更新する
(iii)区間計算クエリ：区間I$I$と値n$n$が与えられ、#{i∈I | ai=n}$\mathrm{\#}\{i\in I|a_i=n\}$を求める

M=(Z5,+),E={(x0,…,x4)↦(x0,x1,x2,x3,x4),(x0,…,x4)↦(0,x0,x1,x2,x3+x4),(x0,…,x4)↦(0,0,x0,x1,x2+x3+x4),(x0,…,x4)↦(0,0,0,x0,x1+x2+x3+x4),(x0,…,x4)↦(0,0,0,0,x0+x1+x2+x3+x4)},f(T)=T$$\begin{gathered} M=({\mathbb{Z}}^5,+), \\ \begin{array}{rl}E=\{& (x_0,\dots ,x_4)\mapsto (x_0,x_1,x_2,x_3,x_4),\\ & (x_0,\dots ,x_4)\mapsto (0,x_0,x_1,x_2,x_3+x_4),\\ & (x_0,\dots ,x_4)\mapsto (0,0,x_0,x_1,x_2+x_3+x_4),\\ & (x_0,\dots ,x_4)\mapsto (0,0,0,x_0,x_1+x_2+x_3+x_4),\\ & (x_0,\dots ,x_4)\mapsto (0,0,0,0,x_0+x_1+x_2+x_3+x_4)\},\end{array} \\ f(T)=T \end{gathered}$$

○余談1
仮定(2)を「f(T)$f(T)$はT$T$に依らずO(1)$O(1)$で計算できる」と弱めるとクエリ当たりO((logN)2)$O((\log N{)}^2)$となる。
ただし、そのかわりに次の条件を仮定するとO(logN)$O(\log N)$で計算可能である。
(2)' f$f$が単射かつf(T),f−1(T)$f(T),f^{-1}(T)$はT$T$に依らずO(1)$O(1)$で計算できる
この場合、各nodeは(x,fk(T))$(x,f^k(T))$の形で情報を持てばよい。
例えば上で挙げた7つの例は全て(2),(2)'の仮定をともに満たす。
(2)と(2)'の仮定をともに満たす場合、各nodeの情報を(x,T)$(x,T)$の形で持つ流儀の人と、(x,fk(T))$(x,f^k(T))$の形で持つ流儀の人がいるため、他人の説明/コードを読む際は、どちらの流儀で書かれたものが注意する必要がある。

○余談1の余談
(2)と(2)'は独立な条件か？
・「(2)を満たし(2)'を満たさないもの」の例としては、区間乗算＋区間総積クエリなどがある。
f(x↦kx)=(x↦k2x)$f(x\mapsto kx)=(x\mapsto k^{2}x)$なので、k=−1$k=-1$のときを考えるとこれは単射ではない。
しかしこれはE′={(n,k) | n,k∈Z≥0}$E^{\prime }=\{(n,k)|n,k\in {\mathbb{Z}}_{\ge 0}\}$で考えることで単射とみなすことができる。
（E′$E^{\prime }$のZ$\mathbb{Z}$への作用は(n,k)(x)=(−1)nkx$(n,k)(x)=(-1{)}^{n}kx$とする）
本質的にダメな例があったら教えて
・「(2)'を満たし(2)を満たさないもの」の例は思いついてないので誰か教えて

○余談2
上で挙げた例は、全てM$M$を適切に取り直すことで、f(T)=T$f(T)=T$とすることができる。
そうすることが出来ない例があったら教えて

*1: よく考えると課すべき条件はT(xy)=(f(T)x)(f(T)y)だったが、ここを変更すると記事全てを書き直す必要があること、現在の条件でも整合性はあること、の2点を理由に修正は行わない