セグメント木がモノイドを必要とする理由

はじめに

セグメント木や遅延セグメント木が扱うデータに対しては、抽象的にはモノイドやモノイド作用付きモノイドであること、また作用の準同型性などが要請されます。この記事では具体的な例や計算を通してそれらの性質が要求される構造を確認していきます。

この記事ではセグメント木や遅延セグメント木についての基本的な理解を前提にしています。もし基本的な部分について知りたい場合は、セグメント木を徹底解説！0から遅延評価やモノイドまでの記事を参考にしていただけると良いと思います。また、モノイドを利用したセグメント木・遅延セグメント木の抽象化についてはモノイド作用付きモノイド, 遅延セグメントツリーを参照いただけるとわかりやすいと個人的に思います。

数学的準備

モノイド

集合$S$とその上の二項演算 $\cdot: S \times S \rightarrow S$が与えられ、以下の条件

• 結合律
  $S$ の任意の元 $a,b,c$ に対して、$(a \cdot b)\cdot c = a \cdot (b \cdot c)$
• 単位元の存在
  $S$ の元 $e$ が存在して、$S$ の任意の元 $a$ に対して $e \cdot a = a \cdot e = a$

を満たすならば、組 $(S, \cdot, e)$ をモノイドといいます。

モノイド作用

$(M, \cdot, 1_M)$ をモノイドとします。集合 $X$ への$M$-作用とは、集合 $X$ と外部演算 $@: X \times M \rightarrow X$の組で、外部演算 $@$ が

• $X$ の任意の元 $x$ について $x@1_M = x$
• $M$ の任意の元 $a, b$ と$X$ の任意の元 $x$ に対して $(x@a)@b = x@(a \cdot b)$

を満たすもののことをいいます。

準同型

準同型とは、数学的構造(特に代数的構造)を保つような写像のことです。
特に、二つのモノイド $(M, \cdot, 1_M)$, $(N, \times, 1_N)$ の間の準同型 $f: M \rightarrow N$ とは、任意の$M$の要素$x,y$について

$$\begin{aligned} f(x \cdot y) &= f(x) \times f(y) \\ f(1_M) &= 1_N \end{aligned}$$

が成り立つような写像のことです。

セグメント木

機能

セグメントツリーは以下のような機能を持ったデータ構造です。

• 代入更新: 任意の値を$\Theta(\log N)$で更新することができる
• 区間取得: 任意の区間に含まれる値の集約値^[1]を$\Theta(\log N)$で求めることができる

必要とされる性質

セグメント木の上で扱う値はモノイドであること、すなわち結合律と単位元が存在することを要求されます。

上記性質を要求する背景

• 結合律を要求する理由
  結合律は、任意の区間に含まれる値の集約値が一意に定まるために必要です。例えば、集約値を求めたい区間に含まれる値が$x_1, x_2, x_3, x_4$だった場合、これらの値の積を求める際に$(x_1 \cdot x_2)\cdot(x_3 \cdot x_4)$と計算する場合や$(x_1 \cdot (x_2 \cdot x_3))\cdot x_4$と計算する場合など色んなパターンが存在しますが、それらの値がすべて等しくなるためには結合律が必要です。
• 単位元を要求する理由
  単位元は、モノイドの積に対して何も影響を与えない値として利用されます。具体的な例としては、セグメント木の配列から完全二分木を構成する際の埋め草として単位元が利用されます。

遅延セグメント木

機能

• 区間更新: 任意の区間に含まれる値を$\Theta(\log N)$で更新することができる
• 区間取得: 任意の区間の値の集約値を$\Theta(\log N)$で求めることができる

必要とされる性質

遅延セグメント木では集約値を求めるための二分木dataと、区間に対して与える作用を溜めておくための二分木lazyの二つを利用して計算を行います。この時、dataとlazy上で扱うデータはそれぞれモノイドである必要があります。ここではdata上のモノイドを$(X,\cdot,1_X)$、lazy上のモノイドを$(M,\times,1_M)$とします。
このとき、$X$に対してモノイド$(M,\times,1_M)$と外部演算$@: X \times M \rightarrow X$の組はモノイド作用となっている必要があり、この作用は次のような準同型性を持つことが必要です。
すなわち、任意の$x,y \in X, m \in M$について

$$(x\cdot y)@m = (x@m)\cdot(y@m)$$

が成り立つことが求められます。

遅延セグメント木に載せるデータに要請される性質を数式の形でまとめると以下のようになります。ただし、$x,x_1,x_2,x_3 \in X,\ m,m_1,m_2,m_3 \in M$はそれぞれ任意にとるものとします。

• 結合律
  • $(x_1 \cdot x_2) \cdot x_3 = x_1 \cdot (x_2 \cdot x_3)$
  • $(m_1 \times m_2) \times m_3 = m_1 \times (m_2 \times m_3)$
• 準同型性
  1. $(x@m_1)@m_2 = x@(m_1 \times m_2)$
  2. $(x_1 \cdot x_2)@m = (x_1@m)\cdot(x_2@m)$

準同型性に関しては、余談でもう少し整理を行います。

上記性質を要求する背景

以下では遅延セグメント木の計算をするにあたってモノイド作用付きモノイド, 遅延セグメントツリーの記述を参考にしています。

二分木data上の値がモノイドであることを要求される理由については、セグメント木の場合の説明と全く同様です。

• 二分木lazy上の値がモノイドである理由

  • 結合律を要求する理由
    lazy上のデータの要素(=作用素)の積の結合の順番は遅延セグメント木に与えられる区間更新・区間取得のクエリに依存しますが、同様の効果を与えるクエリの結果を一意にするためには、結合律が必要になります。
    具体的に、配列$[x_1,x_2]$から生成された遅延セグメント木に次のようなクエリを与えた場合の結果を見てみましょう。

    • パターンA
      1. $[0,2)$に$a \in M$を作用
      2. $[0,2)$に$b \in M$を作用
      3. $[0,2)$に$c \in M$を作用
      4. $[0,1)$の集約値を取得
    • パターンB
      1. $[0,1)$に$a \in M$を作用
      2. $[0,2)$に$b \in M$を作用
      3. $[0,2)$に$c \in M$を作用
      4. $[0,1)$の集約値を取得

    ここで、結合律を仮定せずにA,B両パターンの計算を行うと、Aでは$x_1@((ab)c)$、Bでは$x_1@(a(bc))$となります。

    計算過程

    

    この二つの計算結果が一致し、$x_1@(abc)$となるために、$M$における積には結合律が必要になります。

  • 単位元を要求する理由
    モノイド$(M,\times,1_M)$における単位元は、作用を起こさない要素として使用されます。例えば、区間作用のクエリの対象となっていない部分の区間については、lazyにおける対応するノードに単位元を置くようにします。

• 準同型性1について
  準同型性1は、作用素を合成してから作用させた結果と作用素を一つ一つ作用させる結果が一致するようにするために必要になります。具体例として、配列$[x_1,x_2]$から生成した遅延セグメント木の区間$[0,2)$に作用素$a,b \in M$を作用させる場合を考えます。

  計算過程

  

  このとき、区間$[0,2)$の集約値は$((x_1x_2)@a)@b$である一方、区間$[0,1)$の集約値は$x_1@(ab)$、区間$[1,2)$の集約値は$x_2@(ab)$であり、これらの積は準同型性2を用いて、

  $$(x_1@(ab))(x_2@(ab)) = (x_1x_2)@(ab)$$

  と書くことができます。区間$[0,1)$の集約値と区間$[1,2)$の集約値の積$(x_1x_2)@(ab)$と区間$[0,2)$の集約値$((x_1x_2)@a)@b$は同一の値でなければいけないので、準同型性1が必要であることがわかります。

• 準同型性2について
  作用素を区間に適用させる時に、複数の区間に分割して作用させることを許すために準同型性2が必要になります。具体的な例として、配列$[x_1,x_2]$に対して区間$[0,1)$と区間$[1,2)$に分けてそれぞれに$a \in M$を作用させたパターンAと、区間$[0,2)$にまとめて$a \in M$を作用させたパターンBを考えます。

  計算過程

  

  区間$[0,2)$の集約値はパターンAでは$(x_1@a)(x_2@a)$、パターンBでは$(x_1x_2)@a$となりますが、これらの値は一致することが期待されており、そのためには準同型性2が必要になります。

余談

準同型性についての整理

準同型性1,2(特に1)はぱっと見だと準同型の定義と形が違うように見えるので、より準同型らしく見えるように変形を行いたいと思います。
いま、モノイド$(X,\cdot,1_X)$とモノイド$(M,\times,1_M)$があり、$M$が外部作用$@:X\times M \rightarrow X$によって$X$への作用になっているとします。このとき、

$$x \in X, m \in M, (x,m) \mapsto x@m \in X$$

のように$@m$を作用させる部分を$X \rightarrow X$の写像とみなすことができ、この写像を$f_m: X \rightarrow X$と書くことにします。また、作用する要素$m$を引数に取り準同型写像$f_m$を返すような写像を$f: M \rightarrow \operatorname{Hom}(X,X)$とします。すなわち、$x@m = f_m(x) = f(m)(x)$となります。

• 準同型性2

  準同型性2の式を$f_m$を用いて書き直すと

  $$f_m(x \cdot y) = f_m(x)\cdot f_m(y)$$

  となり、準同型性2の式が準同型性、より特殊には自己準同型性を表していることがわかると思います。

• 準同型性1

  また、準同型性1の式について$f$を用いて書き直すと、

  $$\begin{align*} f(m_1\times m_2)(x) &= f(m_2)(f(m_1)(x)) \\ &= (f(m_2) \circ f(m_1))(x) \\ \iff f(m_1\times m_2) &= f(m_2) \circ f(m_1) \end{align*}$$

  となります。ここで、$\circ'$を写像$f,g$に対して、$g\circ' f \coloneqq f\circ g$となるような演算として定義すると

  $$f(m_1\times m_2) = f(m_1) \circ' f(m_2)$$

  であり、写像$f: M \rightarrow \operatorname{Hom}(X,X)$はモノイド$(M,\times,1_M)$からモノイド$(\operatorname{Hom}(X,X), \circ', f_{1_M})$^[2]への準同型であることがわかります。

十分性

この記事では、モノイドや準同型性がセグメント木・遅延セグメント木の計算に必要であるということを示しましたが、逆にそれらの性質があればセグメント木・遅延セグメント木の計算を行うのに十分であるということには触れていません。よかったら証明してみてください。

付録

付録として、Rustでモノイドを明示的に利用して遅延セグメント木を実装し、典型90問の第29問 Long Bricksを解いたコードを置いておきます。

https://gist.github.com/santamn/58862a3105cc208aa30f50014073f2d2

参考文献

• モノイド
• 準同型
• SegmentTreeに載る代数的構造について
• モノイド作用付きモノイド, 遅延セグメントツリー
• 代数 - モノイド
• セグメント木を徹底解説！0から遅延評価やモノイドまで

脚注

1. この記事で集約とは、モノイドの積とみなすことのできる操作を複数個の値に行うことを指します。

2. これは写像の合成を積とするモノイド$\operatorname{Hom}(X,X)$の逆モノイドになります