遅延セグメント木

この記事では遅延セグメント木の「気持ち」を説明します。
通常のセグメント木に関する知識を前提とします。
アルゴリズムの説明のみであり、実装については一切説明していません。
基本的には以下のサイトの記述を、自分好みにリライトしたものです。
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_i$ を $Ta_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つのことを行う
１． $T$ を子nodeに伝播する。即ち、子nodeが $(x',T')$ であるとき、これを $(x',TT')$ に更新する
（↑これが肝となる遅延伝播）
２．子nodeを再帰的に更新する
３．子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つのことを行う
１． $T$ を子nodeに伝播する。即ち、子nodeが $(x',T')$ であるとき、これを $(x',TT')$ に更新する
２．自身のnodeを、 $\DeclareMathOperator{\id}{id}(f^k(T)(x),\id)$ に更新する
（更新クエリと違って値が変化しないので子を見る必要がない）
３．子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$

○非自明な例１
$\mathbb{Z}$ の数列 $\{a_i\}$ が与えられる。次のクエリに答えよ
(i)区間加算クエリ：区間 $I$ と値 $k$ が与えられ、全ての $i\in I$ について $a_i$ を $a_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$ が写像の合成で閉じていることを確かめよ）

○非自明な例２
$\mathbb{Z}$ の数列 $\{a_i\}$ と $\{b_i\}$ が与えられる。次のクエリに答えよ
(i)区間更新クエリ：区間 $I$ と値 $k$ が与えられ、全ての $i\in I$ について $a_i$ を $a_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$

○非自明な例３
$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_i$ を $a_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)を満たさないもの」の例は思いついてないので誰か教えて