概要
実装が一通り分かってる人向けです。ライブラリを再整備していたらここらへんをまとめたくなったので。
普通のセグ木にモノイドが載るという話は掃いて捨てるほどあるので、やりたいのは主に後の2つです。
2024/02/12 追記
この記事は、SegmentTree に乗る構造に対する曖昧な理解を数学的な言葉を用いて言語化することで理解を深めることを目的に書かれたものです。そのため内容に関して厳密に議論されているとは言い難く、言葉遣いに関しても怪しいところが多いものになっていると思われます。
本記事はこのような欠点を抱えていながら著者の力不足により改稿できていませんでしたが、kimiyuki さんと Shiho Midorikawa さんによる厳密な議論が以下のPDFにて公開されています。このようなことを書くのは他人の努力にただ乗りするようで不誠実でありますが、数学的な議論にある程度慣れている方はもちろん、そうでない方も一読してみることをお勧めします。
使う代数的概念
モノイド
- 関数
fはT f(T a, T b)のように書ける(引数に型Tの要素を2つとり、1つの型Tの要素を返す) -
f(a, f(b, c))=f(f(a, b), c))が成立する(演算の順序を入れ替えても結果が変わらない、結合法則が成立する) - 型
Tのある値をaとする。この時、どんなaについてもf(a, id)=aかつf(id, a)=aが成立する(そのようなidを単位元と呼ぶ)
ここまでは大丈夫でしょうか?具体例で考えてみましょう。
例えば、「整数とaddと0」というペアはモノイドになります。add(a, b)はa+bの言い換えだと思ってください。
上の規則を1つずつ確認していきます。
- 加算は整数と整数を取って整数を返す関数である。
-
add(a, add(b, c))=add(add(a, b), c))である。 - 値
0に対して、どんな整数aについてもadd(a, 0) = aかつadd(0, a)=aとなる。
よって、「整数とaddと0」がモノイドになることが分かりました。いちいち日本語で表記するのはつらいので、今後は(整数,add,0)と表記することにします。
ここで、意識しておいてほしい性質があります。f(a, b)=f(b, a)は必ずしも成立しません。
演算の順序を入れ替えることが許されているとは言っても、左右を逆転することは許されていません。なので、必ずしも成立するとは限らないです。
2つ目は、単位元を持たないものについても、単位元を強制的に作ることができるという性質です。
まず、二項演算fとTのペア(T, f)があったとしましょう。
この時、Tに属さない適当な要素idを持ってきます。そして、f'を「aがidならばbを、bがidならばaを、そうでないならばf(a, b)」を返す関数とします。
そうすると、Tにidという要素を添加した型T'を考えることができ、(T', f', id)はモノイドとなることが分かりました。
他にも、モノイドの例をいくつか上げておきます。
-
乗算(実数を定義域として、1を単位元とする) -
max,min(実数を定義域として、それぞれ-∞,∞を単位元とする) -
排他的論理和(xor) (整数を定義域として、0を単位元とする)
以上が、モノイドの基本的な説明と性質です。
準同型性
ここでは、準同型性の「お気持ち」とモノイドの準同型についての定義をします。
準同型性とは、操作がもつある性質のことです。その性質とは、「ある世界で操作をしてから変換するのと、別の世界に変換してから操作するのが等しい」という性質です。
具体例で確認してみましょう。
例えば、整数の世界と偶数の世界を考えます。ここで、
- 「整数の世界」で足し算をした後、二倍をして「偶数の世界」に移す
- 「整数の世界」から二倍をして「偶数の世界」に移した後、足し算をする
という2つの操作を考えます。これらの操作はどちらも等しくなっていることが分かります。
式で書くと$2\times(a+b)=2\times a+2\times b$のようになり、より分かりやすいですね。
ここで、移す世界の前と後で考える演算が二項演算であるような場合のみについて考えます。
ある写像$f:A\to B$と、関数の定義域$A$/値域$B$で定義される演算$\times,\times^\prime$について、
$f$が$f(a\times b)=f(a)\times^\prime f(b)$を満たす場合これを準同型写像と呼びます。
これを見ると、2つの集合$A$,$B$やその上で行う演算$\times,\times^\prime$が必ずしも同じものである必要がないことが分かります。
例えば、正の実数の集合$\mathbb{R}+$と実数の集合$R$、対数関数$\log$について$\log(a\times b)=\log(a)+\log(b)$という等式が成り立ちます。$a,b$は$R+$の要素であり、$\log$の戻り値は$R$の要素なので、$\log$は準同型写像の例であることが分かります。
先程は2つの集合や演算が別のものでも良いといいましたが、これらが同じ場合を考えると都合が良いことがあります。例えば、モノイド$(R,+,0)$から自身への準同型写像として、$f(x):=-x$が挙げられます。このようなものを、特に自己準同型と呼びます。
$(R,+,0)$について$f(x):=-x$が自己準同型をなすことについては、$-(a+a)=(-a)+(-a),0=-0$であることを確かめることで示すことができます。
前提条件
以下で考える演算は、全て定数時間で計算可能であると仮定する。実際の演算にかかる計算量が $O(a)$ である場合は、全クエリに$O(a\log N)$ の計算量がかかるようになる。
一点更新/区間取得
つまり普通のセグ木。
- 結合則を要求: 区間の併合がしたいので、$a \cdot b \cdot c \cdot d=(a \cdot b)\cdot(c \cdot d)$であってほしい
- 単位元を要求: 最初に配列に入ってる値とか、無の区間とかに作用させても変わらない値として必要1
これはモノイドという構造をなす。ここまでは簡単。
区間更新/一点取得
俗に言う双対セグ木。遅延セグ木の作用素の部分のみを抽出したものとも言える。
- 結合則を要求: 作用素を伝搬するタイミングについて、適用する順番が前後しないことだけを気にしていればいいようにするため
- 単位元を要求: 作用素を伝搬させた後に、何も作用しないということを表すために必要
よって、これもモノイド。
区間加算等の可換モノイドであれば作用素を適用する順番が関係ないため、作用素の伝搬をサボって定数倍改善ができる。
区間更新/区間取得
俗に言う遅延セグ木。
後の議論のために、要素と作用、作用素という概念を導入する。
まず、扱う要素の集合を$M$、作用素の集合を$O$とする。$M$ はセグ木から取得する値の集合となる。また、作用は更新クエリで行われる一要素に対する操作のことである2。
ここで言う作用素は、一般的な数学とかでの作用素とちょっと違うもの。プログラムで扱うにあたって作用を符号化したいというモチベーション。
作用素とは、要素を更新する時に行う作用を代表する値。作用素から作用が一意に定まればなんでもよい。
例えば、$g_x(n):=n+x$ という関数によって表される作用の集合 $\{g_x(n):=n+x|x \in \mathbb{R}\}$ を考える時、$x$を作用素とできる3。
作用素を $o$ としたとき、$o$ によって表される作用を $f_o$ と表記することにする4。
そして、作用素$o$を要素$x$に対して適用させる時、要するに要素に作用させる時は$f_o(x)$と表す。
まず、遅延セグ木を構成するにあたって与えられる引数は $(M,\cdot,id_M,O,\times,id_O,f)$ みたいなペアで表される。前3つは要素のモノイドで、そのあと 3 つは作用素のモノイド。$f$ は $o$ から $f_o$ を作る関数、つまり $f(o):=f_o$。
ここで、この引数が満たすべき要件を述べる。
1: $(M,\cdot,id_M)$ はモノイドをなす
2: $(O,\times,id_O)$ はモノイドをなす
3: $f_{id_O}(x)=x$
4: $f_o(x \cdot y)=f_o(x) \cdot f_o(y)$
5: $f_{o_2}(f_{o_1}(x))=f_{o_1 \times o_2}(x)$
以下説明。
1: $(M,\cdot,id_M)$がモノイドをなすことについては、通常のセグ木と同等なので略。
2: $(O,\times,id_O)$がモノイドをなすことについても、双対セグ木における要素の話と同等。
3: 作用素の単位元が恒等射を表すことについて。これは2,5より導くことができるのでなくても良いが、簡便のためにつけた。
4: 自己準同型性。これがあることにより、作用素を区間に適用させる時に複数の区間に分割して渡して良くなる。([0,3)という区間に作用させる時に、[0,2),[2,3)に分割して作用させることを許している)
5: 作用素が満たすべき要件。作用素を合成させてから作用させるのと、作用素を一つ一つ作用させる結果が同じであって欲しい。
この式についてもう少し詳しく見てみる。はじめに、関数合成の順序が嫌なので$f\circ^\prime g=g\circ f$なる$\circ^\prime$を定義する。これとはじめに定義した関数$f(o):=f_o$を用いて与式を書き換えると、
$
\displaystyle
\begin{eqnarray*}
&&f_{o_2}(f_{o_1}(x))=f_{o_1 \times o_2}(x) \\
&\Leftrightarrow& (f_{o_2} \circ f_{o_1})(x)=f_{o_1 \times o_2}(x) \\
&\Leftrightarrow& f_{o_2} \circ f_{o_1} = f_{o_1 \times o_2} \\
&\Leftrightarrow& f(o_1)\circ^\prime f(o_2)=f(o_1 \times o_2) \cdots (1) \\
\end{eqnarray*}
$
となる。$f$は作用素の集合($O$)から考えている作用の集合への写像で、考えている作用の集合は $M$ についての自己準同型の集合 $Hom(M, M)$ なので、$f$ は $O$ から $Hom(M, M)$ への写像、つまり $f:O→Hom(M, M)$ とも定義できる。$(1)$ 式はこの写像 $f$ の準同型性を表している式であるため、与式は $f$の準同型性 が要件と言い換えることができる。
つまり、遅延セグ木に載るものは
- モノイド$M$とモノイド$O$の組で、$O$からモノイド$(Hom(M, M),\circ^\prime,id_{Hom(M, M)})$への準同型写像$f$が存在するもの
ということになる。
ちなみに、これも$(O,\times,id_O)$が可換モノイド、つまり$\times$が可換であれば伝搬とかを一部サボって高速化できる。