メモ

yukicoderでゆるふわgolf

遅延セグメント木

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


○遅延セグメント木とは

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

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

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

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


○自明な例
区間加算クエリ+区間和クエリ
M=(M,+),\\ E=\{x \mapsto x+k\ |\ k\in M\},\\ f(T)=T^2
区間加算クエリ+区間maxクエリ
M=(M,\max),\\ E=\{x \mapsto x+k\ |\ k\in M\},\\ f(T)=T
区間変更クエリ+区間和クエリ
M=(M,+),\\ E=\{x \mapsto k\ |\ k\in M\}\cup\{\DeclareMathOperator{\id}{id}\id\},\\ f(x \mapsto k)=(x \mapsto 2k)
区間変更クエリ+区間maxクエリ
M=(M,\max),\\ E=\{x \mapsto k\ |\ k\in M\}\cup\{\DeclareMathOperator{\id}{id}\id\},\\ f(T)=T


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

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)
E写像の合成で閉じていることを確かめよ)


○非自明な例2
\mathbb{Z}の数列\{a_i\}\{b_i\}が与えられる。次のクエリに答えよ
(i)区間更新クエリ:区間Iと値kが与えられ、全てのi\in Iについてa_ia_i+b_i kに更新する
(ii)区間計算クエリ:区間I=[l,r)が与えられ、a_l+a_{l-1}+\ldots+a_{r-1}を求める

M=(\mathbb{Z}^2,+),\\ E=\{(a,b) \mapsto (a+bk,b)\ |\ k\in \mathbb{Z}\},\\ f(T)=T


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

M=(\mathbb{Z}^5,+),\\
 \begin{array}{rl}
E=\{&(x_0,\ldots,x_4)\mapsto(x_0,x_1,x_2,x_3,x_4),\\
&(x_0,\ldots,x_4)\mapsto(0,x_0,x_1,x_2,x_3+x_4),\\
&(x_0,\ldots,x_4)\mapsto(0,0,x_0,x_1,x_2+x_3+x_4),\\
&(x_0,\ldots,x_4)\mapsto(0,0,0,x_0,x_1+x_2+x_3+x_4),\\
&(x_0,\ldots,x_4)\mapsto(0,0,0,0,x_0+x_1+x_2+x_3+x_4)\},
\end{array}
\\
f(T)=T


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

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

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

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