セグメント木, より一般に「区間積クエリを高速計算する方法」の圏によるモデル

TL;DR

セグメント木とは, ある半開区間の圏表現$\mathbb{I}$から何らかの圏$C$への関手$F$である. セグメント木の一点・多点更新クエリとは自然変換である.

セグメント木という呼称はあくまで関手の計算グラフのとり方によるものであって, Sparse Table等の(列を計算するための)手法も, 基本的には統一した観点で見ることができる.

はじめに

本記事は「高速計算可能な区間クエリとはどのようなものか」へと圏論的なモデルを与える. 特にセグメント木にフォーカスしているが, [2]における議論を前提とするならば, 本記事の内容はSparse Tableや累積和にも一般化可能であるはずである. ただしそれらに対しては未証明の部分が大きい.

もともとは先日公開した論文[4]における議論から発展したものであるが, @convexineq氏によって計算機科学的視点からのセグメント木・(Disjoint) Sparse Table・累積和等の再整理[2]がなされたことをきっかけに, 代数的モデルも改めて区間積・区間乗算等の(より一般の)形で議論すべきではないかと考え, そのような方針で再整理した. なお, 区間乗算クエリは(記事が長くなってしまったため)別記事に書き起こす予定である.

[2]において議論されているのはあくまで計算アルゴリズムの観点からの議論である. 特に双対セグメント木の双対性を前処理・後処理の観点から説明していることは興味深いところである. なぜならば, 圏論的モデルを与える議論からも全く同じ結論に至っているためだ.

しかしながら, 本記事においてアルゴリズム的な観点は殆ど登場しない. セグメント木において重要なのは「区間積クエリを高速計算するための方法とは何であるか」であって, 「区間積クエリとして計算できるような代数構造とは何であるか」はまた別の問題である. [2]は前者に関するまとめとなっており, 本記事は後者を目指すものである.

準備

本記事では[1]における圏の定義を採用している. しかしこの定義はあまり一般的ではないように思われるため, 本節でこの定義を紹介する. なお, 関手や自然変換といった用語に関しては既知であるものとする (即ち, 本節を読んで初めて圏を知る場合, 本節の内容は意味をなさない).

Def (ファイバー積). 集合$X, Y, S$, 写像$f\colon X \to S$, $g\colon Y \to S$に対し, $$ X\times _ {f, S, g} Y := \lbrace\,(x, y)\mid (x, y)\in X\times Y.\ f(x) = g(y).\,\rbrace $$ と定義する. これを$X$と$Y$の($f$と$g$による)ファイバー積という.

明白な場合, $f$, $g$は省略することもある.

Def (射影). ファイバー積$X\times _ {f, S, g} Y$に対し$\mathrm{pr} _ 1\colon X\times _ {f, S, g} Y\ni (x, y) \mapsto x\in X$, $\mathrm{pr} _ 2\colon X\times _ {f, S, g} Y\ni (x, y) \mapsto y\in Y$をそれぞれ第一成分への射影, 第二成分への射影という.

ファイバー積は幾何学的な貼り合わせ, のりしろの概念を抽象化したものである. これを用いて圏を定義する.

Def (圏). 集合$C$, ${M}$に対し, $s\colon M \to C$, $t\colon M \to C$, $c\colon M\times _ {s, C, t} M \to {M}$, $e\colon C \to {M}$が定義されており, なおかつ次の7つが成立しているとき, またそのときに限り, $(C, M, s, t, c, e)$を圏という. ただし, 集合$S$に対し$1 _ S\colon S\to S$は$S$の恒等写像.

  1. $t\circ c = t\circ \mathrm{pr} _ 1$
  2. $s\circ c = c\circ \mathrm{pr} _ 2$
  3. $c\circ (1 _ M\times c) = c\circ(c\times 1 _ M)$
  4. $s\circ e = 1 _ C$
  5. $t\circ e = 1 _ C$
  6. $c\circ(e\circ t, 1 _ M) = 1 _ {M}$
  7. $c\circ (1_M, e\circ s) = 1 _ {M}$

この定義は[1, p.3, 定義1.2.1]における可換図式(1.3), (1.4)を等式に開いたものである. はてなブログに記事を書く都合上, 可換図式ではなく等式による表現のほうが楽であったため, このような形をとった.

圏$(C, M, s, t, c, e)$はしばしば省略して$C$と書かれる. 多くの場合, 対象の集合(の記号表記)からその圏は文脈上一意に定まるためである. 勿論, 同じ対象に対して異なる圏を考える場合にはこの限りではない.

半開区間からなる圏

本記事において, $\mathbb{I} _ {i\to j}$を半開区間$\lbrack i, j)$による圏として定義する. 本節はその定義を与えるものである.

Def. $i, j\in\mathbb{N}$とする. $i\leq j$のとき, $\lbrack i, j) := \lbrace\,x\mid x\in\mathbb{N}.\ i\leq x\lt j.\,\rbrace$を($i$から$j$への)半開区間という.

$\lbrack i, i) = \emptyset$を許すことに注意. このため$\lbrack 0, 0) = \lbrack 1, 1) = \cdots = \lbrack N, N) = \cdots$のように複数の表現を持ちうる. ただし, 便宜上のラベルとして$(1, \lbrack 1, 1))$のような直積を考えることでこれは弁別可能である.

Prop. 1. 半開区間$\lbrack i, j)$について以下のように定義する.

  • $C := \lbrack i, j)$.
  • $M := \lbrace\,\lbrack a, b)\mid a, b\in\mathbb{N}.\ i\leq a\leq b\leq j.\,\rbrace$
  • $s\colon M \ni \lbrack a, b) \mapsto a\in C$
  • $t\colon M \ni \lbrack a, b) \mapsto b\in C$
  • $c\colon M\times _ {s, C, t} M\ni (\lbrack b, c), \lbrack a, b)) \mapsto \lbrack a, c)\in {M}$
  • $e\colon C\ni a\mapsto \lbrack a, a)\in {M}$

このとき, $\mathbb{I} _ {i\to j} := (C, M, s, t, c, e)$は圏.

Proof. 定義を直接確かめればよい. 以下に登場する半開区間はいずれも$C$の元であるものとする.

  1. $(t\circ c)(\lbrack b, c), \lbrack a, b)) = t(\lbrack a, c)) = c = t(\lbrack b, c)) = (t\circ \mathrm{pr} _ 1)(\lbrack b, c), \lbrack a, b))$
  2. $(s\circ c)(\lbrack b, c), \lbrack a, b)) = s(\lbrack a, c)) = a = s(\lbrack a, b))= (c\circ \mathrm{pr} _ 2)(\lbrack b, c), \lbrack a, b))$
  3. $$ \begin{aligned} (c\circ (1 _ M\times c)))(\lbrack c, d), \lbrack b, c), \lbrack a, b)) &= c(\lbrack c, d), \lbrack a, c))\cr &= \lbrack a, d)\cr &= c(\lbrack b, d), \lbrack a, b))\cr &= (c\circ(c\times 1 _ M))(\lbrack c, d), \lbrack b, c), \lbrack a, b)) \end{aligned} $$
  4. $(s\circ e)(a) = s(\lbrack a, a)) = a = 1 _ C(a)$
  5. $(t\circ e)(a) = t(\lbrack a, a)) = a = 1 _ C(a)$
  6. $(c\circ(e\circ t, 1 _ M))(\lbrack a, b)) = c(\lbrack b, b), \lbrack a, b)) = \lbrack a, b) = 1 _ M(\lbrack a, b))$
  7. $(c\circ (1_M, e\circ s))(\lbrack a, b)) = c(\lbrack a, b), \lbrack a, a)) = \lbrack a, b) = 1 _ M(\lbrack a, b))$

よって成立. $\Box$

セグメント木

Def. 区間$\lbrack 0, N)$と圏$C$について, 関手$F\colon\mathbb{I} _ {0\to N}\to C$をセグメント木という.

上の定義は非直感的であろうと思われるため, 次の命題でこのことを詳しく説明する. なお, 本命題の証明は完全に形式化されているわけではない (厳密には未証明である).

Prop. 2. セグメント木$F\colon\mathbb{I} _ {0\to N}\to C$をとる. $C$における射の合成が$O(1)$で計算でき, また射を空間計算量$O(1)$で保持・表現できるとき, 次が成立.

  1. $\lbrack i, j) \subseteq \lbrack 0, N)$に対し, $F(\lbrack i, j))$は空間計算量$\Omega(N)$で計算できる1.
  2. $\lbrack i, j) \subseteq \lbrack 0, N)$に対し, $F(\lbrack i, j))$は時間計算量$O(\log N)$で計算できる.

Proof.

  1. 任意の$a\in\lbrack 0, N + 1)$に対し, $F(\lbrack a, a))$は$F(a)$の単位射へと移るため, $F(\lbrack i, j)) = F(\lbrack j-1, j))\circ F(\lbrack j-2, j-1))\circ\cdots\circ F(\lbrack i, i + 1))$より, $F$の計算には長さ1の区間全てに対応する値を持っていればよい. したがって, $a _ i := F(\lbrack i, i + 1))$とするとき, $a _ 0, a _ 1, \ldots, a _ {N - 1}$が計算のために最低限必要な元である.
  2. 計算したいものは(1.)と同様に長さ1の半開区間の像の合成である. 射の全体はモノイドをなすことから, これはモノイドの区間積演算の議論をそのまま適用できる. よって, [2]における計算グラフの前計算を実施することによって達成できる. $\Box$

Prop. 2 (2.)はそのままセグメント木に載せることを言っている. この点は[2]において議論されているものそのままであり, 特に難しい話ではない. 重要なのは, Prop. 2 (1.)にある通り, 区間の圏からの関手は列を中に持ち, またその計算結果全体を同時に持つことである. このことをもって, 我々が「区間積クエリ」と呼んでいるものは関手の計算に等しいと言えるのである.

この定義に沿えば, 「セグメント木に乗る代数構造」とは圏$C$のことである. 「セグメント木に乗る構造は圏である」という主張[3]はこのように表現される.

一点更新クエリについて

ここまで関手の計算に触れてきたわけだが, 関手の計算だけではあくまでオフラインの(更新の無い)アルゴリズムとしてしか扱えない. そこで, 一点 / 多点更新クエリがどのように形式化されるのかに関して本節で検討する.

まず素朴な観察として, モノイド${M}$を載せたセグメント木においては自由に更新できる.

次に, 実数値行列の全体からなる圏$C$を考えよう. 対象は$\mathbb{N}\setminus\lbrace\,0\,\rbrace$, 射$i \to j$は$i\times j$行列である. このとき$\mathbb{I} _ {0\to 4}\to C$なるセグメント木において次のような設定であるものを考えられる:

  • $F(0) = 1$, $F(1) = 2$, $F(2) = 3$, $F(3) = 4$, $F(4) = 5$
  • $F(\lbrack i, j))$: $i\times j$行列
  • $F(\lbrack j, k))\circ F(\lbrack i, j))$: $i\times j$行列と$j\times k$行列の積

言い換えれば, この関手$F$は[1x2行列, 2x3行列, 3x4行列, 4x5行列]を管理しているわけである. そしてこの場合, 更新できない場面を考えなければならない. 具体的には「0番目を2x3行列にする」という操作はこのセグメント木に対しては無効である (2x3行列と2x3行列の積は計算不可能). この要件はその上に載っている代数構造の制約から来ているものであり, それゆえ「セグメント木の一点更新は代数的な意味をもたなければならない」という仮説をたてられるのである.

さて, セグメント木$F\colon\mathbb{I} _ {0\to N} \to C$, $G\colon\mathbb{I} _ {0\to N} \to C$を取り, この間に次の条件が課されている場合を考えよう: $F\colon\mathbb{I} _ {0\to N} \to C$, $G\colon\mathbb{I} _ {0\to N} \to C$をセグメント木とする. ある$i$が存在して$F(\lbrack i, i+1)) \ne G(\lbrack i, i+1))$であり, なおかつ$j\ne i$なる任意の$j\in \lbrack 0, N)$に対して$F(\lbrack j, j+1)) = G(\lbrack j, j+1))$である.

よりinformalに言えば, この条件は「一点だけ違う列」という条件である. このように翻訳することで, 一点更新クエリの可能性とは「この関手の間に自然変換を構成できるだろうか?」という問題と本質的に同じであることがわかる (一般の場合は多点更新クエリとして取り扱う).

実際, モノイドに対しては一般に自然変換を構成できる. このことを以下に示す.

Thm. 3. セグメント木$F\colon\mathbb{I} _ {0\to N} \to C$, $G\colon\mathbb{I} _ {0\to N} \to C$に対し, $\delta\colon F(N)\to G(0)$が存在するものとする. このとき, 自然変換$\theta\colon F\Rightarrow G$がある. 換言すれば, 多点更新クエリの十分条件は$\delta$の存在である.

Proof. $\theta _ k := G(\lbrack 0, k))\circ \delta\circ F(\lbrack k, N))$とおく. $G(\lbrack 0, 1))\colon G(0)\to G(1)$, $F(\lbrack N - 1, N))\colon F(N-1)\to F(N)$であるから, $G(\lbrack 0, k))\circ \delta\circ F(\lbrack k, N))$は$F(k)\to F(N)\to G(0)\to G(k)$なる射の合成として意味をもつ. このとき任意の$\lbrack i, j)\in\mathbb{I} _ {0, N}$について $$ \begin{aligned} \theta _ j\circ F(\lbrack i, j)) &= G(\lbrack 0, j))\circ \delta\circ F(\lbrack j, N))\circ F(\lbrack i, j))\cr &= G(\lbrack 0, j))\circ \delta\circ F(\lbrack i, N))\cr \end{aligned} $$ $$ \begin{aligned} G(\lbrack i, j))\circ \theta _ i &= G(\lbrack i, j))\circ G(\lbrack 0, i))\circ \delta\circ F(\lbrack i, N))\cr &= G(\lbrack 0, j))\circ \delta\circ F(\lbrack i, N))\cr \end{aligned} $$ である. それぞれ一致するため成立. $\Box$

Cor. 4. セグメント木$F\colon\mathbb{I} _ {0\to N} \to C$, $G\colon\mathbb{I} _ {0\to N} \to C$に対し, $C$がモノイドであるならば, 多点更新クエリを実行できる.

Proof. モノイドにおいて対象は唯一つであるため, $F(N) = G(0)$である. ゆえに$\delta$として恒等射をとればThm. 3より成立. $\Box$

先に見たような行列積演算もCor. 4同様に取り扱える. なぜならば, $F(N)\times G(0)$行列として適当な行列をとればこれを満たすからである.

セグメント木の合成

[4]において触れていた話題の一つに, セグメント木の合成を考えていたものがあった. これは次の定理で存在を保証される.

Thm. 5. セグメント木$F\colon\mathbb{I} _ {0\to N}\to C$, $G\colon\mathbb{I} _ {0\to N}\to D$をとる. このとき$F\times G\colon \mathbb{I} _ {0\to N}\to C\times D$はセグメント木.

Proof. 自明. $\Box$

おわりに

双対セグメント木ぐらいは書きたかったのだが, セグメント木だけでも分量過多になってしまっている. 現時点で双対セグメント木は以下の通り定義されており, 次の記事ではこれをもとに双対セグメント木・遅延伝播セグメント木の上に乗る構造について, その圏論的モデルを与える予定である.

Def. 区間$\lbrack 0, N)$と圏$C$, $D$について, 関手$F\colon D\to \mathrm{Fun}(\mathbb{I} _ {0\to N}, \operatorname{End}(C))$を双対セグメント木という.

双対セグメント木はセグメント木の一種であるが, 自己関手を得るための前段階が挟まっているのが特徴である. また, 最終的に得られるものはあくまで自己関手である. そうやって得られた自己関手を適用する操作は利用する側の都合であり, あくまで双対セグメント木が行っている操作は「一点取得」ではなく「関手を得る操作」であると解釈すべきであろう.

遅延伝播セグメント木はセグメント木と双対セグメント木を組み合わせたものである. 即ち, 「区間から圏への関手」「区間に応じて自己関手への関手を与える関手」の二つが遅延伝播セグメント木を構成している.

[4]で触れたような合成の議論は関手圏における圏論的直和を効率的に計算できるかどうかに関わっている. しかしながら, 未だ議論し尽くせていないように思えているのも事実であり, 目下この点が最大の研究課題と見ている.

本記事は「セグメント木に対する更新クエリは自然変換である」と主張しているわけだが, その自然変換を与えるための必要十分条件に関しては未だ議論し尽くせていない. 随伴関手を与えるとどうなるかについて現状考えている状態であるが, 上手なまとまり方はしていないため, future workとしてこの点も検討しておきたい. 自然変換の計算量を込みに考えた場合も同様である.

References

  1. 斎藤毅. 2020. 数学原論. 東京大学出版会.
  2. @convexineq. 2021. 半群の区間積クエリについて. https://qiita.com/convexineq/items/4b6920af3e3d37a96540
  3. @kimiyuki_u. 2018. セグメント木の上に乗る構造はモノイドではなく圏である. - https://kmyk.github.io/blog/blog/2018/12/06/categories-on-segment-tree/
  4. @kimiyuki_u and @elliptic_shiho. 2021. セグメント木と代数構造の理論. https://elliptic-shiho.github.io/segtree/segtree.pdf
  1. 動的セグメント木のような形で, 必要に応じて区間を作ることにするのであればこの限りではない. しかしそれはオンラインアルゴリズムである前提を置いているために成立する工夫であって, 今回の前提からは外れる.↩