概要
実装が一通り分かってる人向けです。ライブラリを再整備していたらここらへんをまとめたくなったので。
普通のセグ木にモノイドが載るという話は掃いて捨てるほどあるので、やりたいのは主に後の2つです。
使う代数的概念
モノイド
- 関数
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つ目は、単位元を持たないものについても、単位元を強制的に作ることができること。
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つの操作を考えます。これらの操作はどちらも等しくなっていることが分かります。
式で書くと$2\times(a+b)=2\times a+2\times b$のようになり、より分かりやすいですね。
ここで、移す世界の前と後で考える演算が二項演算であるような場合のみについて考えます。
ある写像$f:A→B$と、関数の定義域$A$/値域$B$で定義される演算$\times,\times^\prime$について、
$f(a\times b)=f(a)\times^\prime f(b)$を満たすような写像$f$を準同型写像と呼びます。
これを見ると、2つの集合$A$,$B$やその上で行う演算$\times,\times^\prime$が必ずしも同じものである必要がないことが分かります。
例えば、正の実数の集合$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$とする。
作用素とは、要素を更新する時に行う作用を代表する値。作用素から作用が一意に定まればなんでもよい。
例えば、$g_x(n):=n+x$ という関数によって表される作用の集合 $\{g_x(n):=n+x|x \in \mathbb{R}\}$ を考える時、$x$を作用素とできる2。
作用素を $o$ としたとき、$o$ によって表される作用を $f_o$ と表記することにする3。
そして、作用素$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$が可換であれば伝搬とかを一部サボって高速化できる。