遅延評価セグメントツリーを一般化すると、モノイドとその作用で書ける、とのことで、自分ライブラリを整理がてら勉強したメモ。

セグメントツリーは、長い配列に格納したデータに対し、その区間を値を走査して値を返す「クエリ」を効率的に実施するためのアルゴリズム。例えば区間和や区間XOR、区間最小など。また、それらのクエリの間にデータの一部を書き換える操作が入ることもある。1つの値を書き換えたり、加算したり、ある区間の値を書き換えたり、加算したり。

クエリ値のモノイド A

長さNの配列をA(N)とし、そのデータ型をTAとする。int や long long、modint などを想定すればよい。Nは$${ 10^5 }$$ 程度を想定する。また、$${A}$$ で型TAの値の集合を表すこととする。ここで、「区間を走査して値を得る」操作を、$${A}$$ の演算として定義でき、かつ、$${A}$$ はその演算によってモノイドになるとする。つまり、$${A}$$ の上に演算

$$
A \times A \rightarrow A: (a,b) \longmapsto a \oplus b \in A
$$

と、単位元 $${e \in A}$$ が定義されて、この演算が結合法則 $${ (a \oplus b) \oplus c = a \oplus (b \oplus c) }$$ を満たし、また単位元 $${e}$$ として $${e \oplus a = a \oplus e = a}$$ なる $${A}$$ の元があるとする。

例えば、$${A = \mathbb{N} }$$（自然数全体） と演算 + は、0を単位元としてモノイドであるし、$${A = \mathbb{Z} \cup \infty }$$ とすれば通常の順序における演算 = min と単位元 = $${\infty}$$ でモノイドとなる。

$$
(a + b) + c = a + (b + c),  0 + a = a + 0 = a \\
\min ( \min(a, b), c) = \min ( a, \min(b, c)),  \min(\infty,a) = \min(a, \infty) = a
$$

「区間を走査して値を得る」演算はこれらを繋げて

$$
A \times … \times A \ni (a_l, a_{l+1}, …, a_r) \longmapsto a_l \oplus a_{l+1} \oplus … \oplus a_r \in A
$$

と書ければOK。

この $${A}$$ の要素列 A(N) を単純なベクトルではなく、二分木に入れて持っていれば、A(N) の区間に対してその演算結果を高速に返すクエリを書くことができる。具体的には、二分木にはあらかじめ計算済みの区間を$${2^k}$$ の長さずつで備えておいて、求めたい区間に応じてそれらを集めればよい。区間が長ければ長い計算済みパーツを使うことができるし、短ければその長さに応じた長さのパーツを採用することで、計算量を$${\mathcal{O}(N)}$$ から $${ \mathcal{O}(\log N)}$$ に落とすことができる。

作用 Z および モノイド Z としての演算

さて、A(N) の値を参照するだけなら上の二分木で十分なのだが、さらに A(N) の値を更新もしたい。例えば、A(N) の中の一つの値 A[i] の値を入れ替えたり、数を加算したり、または A(N) の区間 A[l,r) の値を一斉に入れ替えたり。そこでこの操作を、別の集合 $${Z}$$ の元 $${z \in Z}$$ を使って $${ f_z }$$ と表せるとする。つまり、

$$
Z \times A \ni (z,a) \longmapsto f_z(a) \in A
$$

 で、$${A}$$ の値を変換する。さらに、この作用が$${A}$$の演算と可換であること、および $${Z}$$ の演算としてモノイドであることを仮定する。つまり、演算 $${ z \circ w }$$ と単位元 $${ e_Z }$$ があって、

$$
f_z(a \oplus b) = f_z(a) \oplus f_z(b),  \\
(z \circ w) \circ v = z \circ (w \circ v),   e_Z \circ z = z \circ e_Z = z
$$

が成り立つとする。$${e_Z}$$ は $${A}$$への作用として必ずしも恒等写像ではない（本当？）が、簡単のため恒等写像であるとしておく。つまり、$${f_{e_Z}(a) = a}$$ とする。

これで遅延評価セグメント木を表現する道具が揃った。

値の更新と遅延評価

A(N) に入っている値をクエリするだけなら、二分木を使えば $${\mathcal{O}(\log N)}$$ で計算することができた。では、値の更新はどうするか。

まず、更新する値が1つのセルだけならば、二分木の更新は $${\mathcal{O}(\log N)}$$ でできる。なぜなら、更新するセルの値およびそれが含まれる二分木上位の値を更新すればよく、その個数は $${\mathcal{O}(\log N)}$$ 個だからである。

問題は、区間更新の場合にある。区間更新の対象となる区間長は$${\mathcal{O} (N) }$$ 個あり、全てのセルを更新すると $${\mathcal{O}(N)}$$ の時間が掛かるため、NG。

そこで「遅延評価」を使う。つまり、区間を更新しようとしたとき、その区間にすっぽり入る「親区間」については親区間のみを更新し、その子区間は放置する。そうすると、区間が長ければすっぽり入る区間を長く取ることができるので、親区間だけ更新され、計算量は $${\mathcal{O}(\log N)}$$ に減る。

しかし、放置した子区間も、別のクエリや別の更新によってちゃんと見なければならない時が訪れるかもしれない。ならば、そのときになってから、それまで積み上がった更新を実行した後、本当にやりたかった操作を実施すればいいじゃないか。つまり、更新を遅延させておいて、必要になってから実施するという方法をとる。

ここで先の$${Z \times Z \rightarrow Z}$$ の演算が活きてくる。操作の遅延分は、その親セルを分割しなければならない事態が来るまで何度も訪れる可能性があるが、その何度も訪れた分を一つの$${Z}$$ の値として保存しておくことができる。最初に来た遅延分が $${z}$$ だったとして、次にまた遅延分 $${w}$$ が来たら、それら二つを保存するのでは無く、$${w \circ z \in Z}$$ なる一つの値に縮約済みにして保存しておけばよい。$${ f_w \circ f_z(a) = f_{w \circ z}(a) }$$ なので、それで十分。

そのようにして、遅延分は全部積み上げて縮約済みにしておいて、必要なときだけ作用させることによって、区間更新についても $${\mathcal{O}(\log N)}$$ で実施できるようになった。その結果、区間更新の回数を$${M}$$、クエリ回数を $${K}$$ とすると、計算量は $${ \mathcal{O}((M+K) \log N) }$$ となるので、例えば $${N = M = K = 10^5}$$ 程度でも十分速い。