セグメント木の理屈を学ぶ(4) 圏への持ち上げ

前回、遅延セグメント木を扱いましたが、今回は一旦遅延は忘れてセグメント木に戻り、扱うことができる構造をモノイドから一般化することを考えます。(遅延構造まで考えると手に負えなくなりました)

第2回目の続きに近い内容です。

先行研究

セグメント木に圏が載る、という主張は “セグメント木の上に乗る構造はモノイドではなく圏である” ¹ などでなされており、“セグメント木, より一般に「区間積クエリを高速計算する方法」の圏によるモデル” ² ではセグメント木を半開区間から圏への関手として捉えています。“セグメント木に圏が乗るか？” ³ でも同様の定式化がされています。

今回は本質的にはこれらとかなり近い内容になります。

前提

• 前回までの設定と記法を引き継ぎます。
• 圏、関手、自然変換は定義のレベルで使います。圏はすべて small とします。対象の集合を $\mathrm{Ob}(C)$、射の集合を $\mathrm{Mor}(C)$, 射 $f$ の始域・終域を $\mathrm{dom}(f), \mathrm{cod}(f)$ と書きます。
• 合成は図式順に書きます。すなわち $f : X \to Y$, $g : Y \to Z$ に対し $f \cdot g : X \to Z$ が「まず $f$、次に $g$」を表します(通常の $g \circ f$ のことです)。前回までの積の記法をそのまま使いたいためです。

具体例から考える: 連鎖行列積

先行研究にも出てくる例を考えます。各 $i$ に $H_i \times W_i$ 行列 $A_i$ が乗っていて、$W_i = H_{i+1}$ が成り立っているとします。このとき区間 $[l, r)$ の区間積

は意味を持ちます。一方 $A_0 A_2$ のような積は一般には定義されないので、$A_i$ たちの全体はモノイドになるとは限りませんが、常に隣接するものどうしの積が計算できれば十分なので、この状況はセグメント木で扱えます。

行列の全体は次のような圏 $\mathbf{Mat}$ を成します。

• 対象: 正の整数
• 射 $i \to j$ : $i$ 行 $j$ 列の実行列
• 合成: 行列の積(図式順に書いているので、$A : i \to j$ と $B : j\to k$ の合成 $A\cdot B$ はそのまま積 $AB$)
• 恒等射 $\mathrm{id}_i$ : $i$ 次単位行列

これが、セグメント木をちょいと拡張してモノイド以外のものも扱えることにしておきたい理由の一つですね。

配列の空間に変わるもの

モノイドで考えていた時は、モノイドからなる任意の配列 $M^n$ が管理できましたが、圏の場合は合成可能な射のみを考える必要があります。

圏 $C$ に対して、 $n$ 個の射の合成可能な鎖の集合を

と書きます。$a \in N_n(C)$ に対して対象の列 $X_0,\ldots,X_n$ が $a_i : X_i \to X_{i+1}$ によって定まります。区間 $[l, r), 0 \le l \le r \le n$ に対する区間積は

で、空区間 $l = r$ のときは $\mathrm{id}_{X_l}(= \mathrm{id}_{X_r})$ と約束します。半開区間では区間の両端がそのまま始域・終域になるので、閉区間のときのような「$r+1$」のずれが消え、空区間の場合の約束も不自然さなく書けます。

$C$ がモノイド(対象がひとつの圏)なら、合成可能性の条件は自動的に満たされるので $N_n(C) = M^n$ となり前回の場合と一致します。

区間からの関手

$N_n(C)$ を区間からの関手と同一視していきます。全順序集合 $0 < 1 < \cdots < n$ を圏と見たものを $[n]$ と書きます。$i \le j$ のとき唯一の射 $i \to j$ が存在する圏です。そうすると、

が成り立ちます。関手 $F : [n]\to C$ を与えることは、対象 $F(0),\ldots,F(n)$ と、隣接する射 $F(i \to i+1)$ を与えることと同じです(それ以外の射の像は合成で決まり、恒等射の像は恒等射に決まります)。

この見方は elliptic-shiho 氏² と p進大好きbot 氏³ の両方が採用しているものです。

後者は「セグメント木に乗るのは小圏そのものではなく、区間から小圏への関手である」という形で強調しています。「圏が乗る」と言うと、モノイドのときと同じように「圏の射からなる任意の配列が管理できる」と読めてしまうが、文字通りには正しくない、という指摘です。

状態空間と $\pi_d$

木の側も定義しておきます。今までと同様に、深さ $d$ の完全二分木のノード集合を $T_d$、葉の数を $n = 2^d$ とし、内部ノード $\tau$ の左右の子を $\mathrm{lch}(\tau), \mathrm{rch}(\tau)$ と書きます。各ノード $\tau$ には半開区間 $\mathrm{seg}(\tau) = [x, y) \subseteq [0, n)$ が対応します。根は $\mathrm{seg}(\tau_0) = [0, n)$、葉は $\mathrm{seg}(\tau) = [i, i+1)$ です。

モノイドのときの整合性条件は $v_{\mathrm{lch}(\tau)}\cdot v_{\mathrm{rch}(\tau)} = v_\tau$ でした。圏では、この等式を書く前に左辺が意味を持つかどうかを問う必要があります。積 $v_{\mathrm{lch}(\tau)}\cdot v_{\mathrm{rch}(\tau)}$ が定義されるとは $\mathrm{cod}(v_{\mathrm{lch}(\tau)}) = \mathrm{dom}(v_{\mathrm{rch}(\tau)})$ のことなので、条件をふたつ並べて

と書けます。

ついでに両端の対象を取り出す写像も用意しておきます。$v \in \mathrm{Seg}_d(C)$ に対し根の値 $v_{\mathrm{root}}$ は $C$ の射なので

と定めます。鎖の側にも同じ名前で

を定めておきます。$a$ の定める対象の列 $X_0,\ldots,X_n$ でいえば $X_0$ と $X_n$ のことです。

実装の見直し

セグメント木では set, query を下のように定義していました。

set(i, c, τ):
  if seg(τ) = [i, i+1):
    v[τ] ← c            # 葉なので直接書き換え
    return
  if i ∈ seg(lch(τ)):
    set(i, c, lch(τ))
  else:
    set(i, c, rch(τ))
  v[τ] ← v[lch(τ)] · v[rch(τ)]     # 子の更新後に再計算

query(l, r, τ):
  if seg(τ) ∩ [l, r) = ∅:
    return e             # 単位元(何も無ければ影響しない)
  if seg(τ) ⊆ [l, r):
    return v[τ]           # 部分木を丸ごと使える
  return query(l, r, lch(τ)) · query(l, r, rch(τ))

query でモノイドの単位元 $e$ を返していましたが、圏では各対象に対して恒等射があることしか保証されていないので、モノイドのように掛けたときに計算結果を変えない単位元をとりあえず返すようなことができません。

1. 任意の射の合成に対して、元々の射を保つ 吸収元 を導入して、 $e$ の代わりに返す: とりあえずこのやり方でセグメント木として動かすことはできます。実装としては、こちらのようになっていることが多そうです。吸収元と書きましたが、射の合成の条件を厳密に考えると怪しいですね。
2. 恒等射を返すように、 query 自体を下のように書き換える:

query(l, r):
  if l = r:
    return id_{X(l)}         # ここだけ特別扱い
  return query(l, r, τ0)

query(l, r, τ):
  if seg(τ) ∩ [l, r) = ∅:
    error # 呼び出しを禁止
  if seg(τ) ⊆ [l, r):
    return v[τ]
  if seg(lch(τ)) ∩ [l, r) = ∅:
    return query(l, r, rch(τ))
  else if seg(rch(τ)) ∩ [l, r) = ∅:
    return query(l, r, lch(τ))
  else:
    return query(l, r, lch(τ)) · query(l, r, rch(τ))

AC Library の Segtree のシグネチャは

(1) segtree<S, op, e> seg(int n)
(2) segtree<S, op, e> seg(vector<S> v)

• 型 S
• 二項演算 S op(S a, S b)
• 単位元 S e()

でした。この S e() を $k = 0, ..., n$ に対する恒等射 $\mathrm{id}_{X_k}$ を返す S id(int k) に置き換えて segtree<S, op, id> にするような考えです。

$\mathrm{seg}(\tau)\cap[l,r) = \emptyset$ となる呼び出しを禁止していますが、正しい呼び出し列の範囲では error になることはありません。呼び出し側で責任を持って使ってくださいという考えですね。

これ以降は2を前提にして考えることにしましょう。すると、前々回の命題7と同様にして状態空間と木の同型が証明できます……とまでは行きません。モノイドのときは深さ $d+1$ の木を左右の部分木の直積として貼り合わせていましたが、圏では貼り合わせる境界で積が定義されていることを保証するため、直積をファイバー積に取り替えなければいけません。

命題 16

$\pi_d : \mathrm{Seg}_d(C) \to N_n(C)$(葉への制限)は全単射であり、かつ両端の対象と両立する。すなわちすべての $v$ について $\mathrm{src}(\pi_d(v)) = \mathrm{src}(v)$ と $\mathrm{tgt}(\pi_d(v)) = \mathrm{tgt}(v)$ が成り立つ。さらにその逆写像は $\pi_d^{-1}(a)_\tau = \mu_{\mathrm{seg}(\tau)}(a)$ で与えられる。

証明. $d$ についての帰納法で、全単射性と両立性を同時に示す。

$d = 0$ のときは $\mathrm{Seg}_0(C) = \mathrm{Mor}(C) = N_1(C)$ で $\pi_0$ は恒等写像なので、どちらも自明。

$d$ について成り立つとして $d+1$ を示す。第2回の補題8(再帰的分解)は、深さ $d+1$ の木の状態を与えることが、深さ $d$ の部分木の状態の組 $(v_L, v_R)$ であって根どうしの積が定義されるものを与えることと同じということだったが、これは圏でもそのまま成立する。根どうしの積が定義される条件はは $\mathrm{tgt}(v_L) = \mathrm{src}(v_R)$ と書けるので、同型

が得られる。(右辺は $\mathrm{tgt}$ と $\mathrm{src}$ に沿ったファイバー積、つまり $\mathrm{tgt}(v_L) = \mathrm{src}(v_R)$ を満たす組 $(v_L, v_R)$ の全体)。

同じ理由で、鎖の側にも前半と後半に切り、$\mathrm{cod}(a_{2^d - 1}) = \mathrm{dom}(b_0)$ で貼り合わせる

が存在する。

ここで制限なしの直積の間の写像 $\pi_d\times\pi_d : \mathrm{Seg}_d(C)\times\mathrm{Seg}_d(C) \to N_{2^d}(C)\times N_{2^d}(C)$ を考えると、帰納法の仮定よりこれは全単射である。あとはこれが両辺のファイバー積の部分に制限されることを言えばよく、そのためには

を確かめれば十分。右辺は、帰納法の仮定の両立性を左右それぞれに使えばそのまま左辺となるため、 $\pi_d\times\pi_d$ を制限しても全単射。

以上と補題8の同型を合わせれば $\pi_{d+1}$ は全単射。 $v \leftrightarrow (v_L, v_R)$ のとき $v_{\mathrm{root}} = (v_L)_{\mathrm{root}}\cdot(v_R)_{\mathrm{root}}$ なので $\mathrm{src}(v) = \mathrm{src}(v_L)$, $\mathrm{tgt}(v) = \mathrm{tgt}(v_R)$ であり、鎖の側でも連結した鎖の両端は前半の始域と後半の終域なので、それぞれに帰納法の仮定を使えば両立性も同時に従います。

逆写像が $\mathrm{Seg}_d(C)$ に属することも前回と同様で、親の区間が子の区間の順序を保った disjoint union であることから、親の積が子の積の合成に等しく、特にその合成が定義されていることも同時に分かります。$\blacksquare$

積がファイバー積に変えると、両立性を示すために命題に条件を入れる必要が出てきました。 $C$ がモノイドなら $\mathrm{Ob}(C)$ は一点なので、ファイバー積は直積に戻って前回の証明と同じになります。

壊れるところ: 更新の定義域が積でない

前回、配列側の更新は

という全域写像でした。木側の $\mathrm{Set}_i$ はこれを $\pi_d$ で移送したものとして一意に定まりました。

圏では、$a \in N_n(C)$ の $i$ 番目を $c$ に取り替えた列が再び $N_n(C)$ に属するために、$c$ の型が $a_i$ と揃っていることが要ります。$a_i : X_i \to X_{i+1}$ だったら取り替える時も $c : X_i \to X_{i+1}$ の形で書けないと型が合わないということですね。すなわち

です。逆にこれさえ満たしていれば、$i$ 番目以外の隣接関係はどこも変わらないので、取り替えた列は $N_n(C)$ に属します。つまり $\mathrm{set}_i$ の定義域は直積ではなく、両端の対象を取る写像

に沿ったファイバー積

が正しい形です。ここでも直積がファイバー積に化けていて、 $C$ がモノイドなら $\mathrm{Ob}(C)^2$ は一点なので条件は空になり、$M\times M^n$ に戻ります。

木側も同じです。$\pi_d$ は葉への制限そのものなので、葉 $i$ の値は $a_i$ そのものであり、$\partial_i$ は木の側でもそのままの意味を持ちます。よって

と定めれば、前回と同様、$\pi_d$ を通じた同一視のもとで配列側の更新と木側の更新は同じ操作になります。命題8 の全単射を両側の(同じ条件で切り出した)部分集合に制限しているだけですね。

ここで壊れるのが「任意の値に更新できる」という部分で、モノイドのときは好き勝手な値に 1 点更新できましたが、圏では型の合う射にしか取り替えられません。列の途中の対象 $X_i$ を別のものに変えたければ $a_{i-1}$ と $a_i$ を同時に更新するしかなく2点以上更新が必要になりますね。連鎖行列積でいえば、行列の中身は自由に差し替えられますが、行列のサイズを変えるには隣も一緒に差し替える必要があります。

一方、$\mu_{[l,r)}$ は $N_n(C)$ 上で全域なので、区間積はそのまま持ち上がります。ただし空区間($l = r$)だけは注意が必要で、 $\mathrm{id}_{X_l}$ を $l$ ごとに識別して返す必要があるので、 query を書き換えていたわけです。

値の置き換えは関手

第2回では、モノイドの準同型 $f : M\to N$ に対して成分ごとの適用 $\mathrm{Seg}_d(f)$ が定まり、これが操作と可換することを見ました。「$\mathbb{Z}$ 上で計算してから $\bmod\ m$ を取っても、最初から $\mathbb{Z}/m$ 上で計算しても同じ」でしたね。

圏でこれに対応するものを考えましょう。

命題17

写像 $\Phi : \mathrm{Mor}(C)\to\mathrm{Mor}(D)$ が次を満たすとする。

1. 成分ごとの適用が $\mathrm{Seg}_1(C) \to \mathrm{Seg}_1(D)$ を定める。すなわち $v \in \mathrm{Seg}_1(C)$ ならば $\Phi(v) \in \mathrm{Seg}_1(D)$。
2. 各対象 $X$ について $\Phi(\mathrm{id}_X)$ は $D$ の恒等射である。

このとき、$\Phi_0(X) := \mathrm{dom}(\Phi(\mathrm{id}_X))$ と定めれば $(\Phi_0, \Phi)$ は関手 $C \to D$ である。逆に、関手はすべての $d$ について $\mathrm{Seg}_d(C)\to\mathrm{Seg}_d(D)$ を誘導し、区間積と可換する。

証明. 深さ 1 の木、すなわち根とふたつの葉だけからなる木を 3 通りに使う。以下 $f : X\to Y$, $g : Y\to Z$ とする。条件 2 より $\Phi(\mathrm{id}_X)$ は恒等射なので、その始域を $\Phi_0(X)$ と書けば $\Phi(\mathrm{id}_X) = \mathrm{id}_{\Phi_0(X)}$ である。

葉に $(\mathrm{id}_X, f)$ を置くと、根は $\mathrm{id}_X \cdot f = f$ であり、この状態は $\mathrm{Seg}_1(C)$ に属する。条件 1 より像 $(\mathrm{id}_{\Phi_0(X)}, \Phi(f))$、根 $\Phi(f)$ は $\mathrm{Seg}_1(D)$ に属する。特に $\mathrm{id}_{\Phi_0(X)}\cdot\Phi(f)$ が定義されるので、$\mathrm{dom}\Phi(f) = \Phi_0(X)$ を得る。葉に $(f, \mathrm{id}_Y)$ を置けば同様に $\mathrm{cod}\Phi(f) = \Phi_0(Y)$ である。

葉に $(f, g)$ を置くと根は $f\cdot g$ であり、条件 1 より $\Phi(f\cdot g) = \Phi(f)\cdot\Phi(g)$ を得る。

以上より $\Phi$ は始域・終域を $\Phi_0$ を通じて保ち、合成と恒等射を保つので関手である。逆は明らかで、関手が合成可能性と合成を保つことから整合性条件が保たれ、区間積との可換性も空区間の場合を恒等射の保存で処理すれば従う。$\blacksquare$

対象の写像 $\Phi_0$ を与えなくても、深さ 1 のセグメント木が壊れないことを要求するだけで関手としての性質が導出されるのが面白いですね。

前回、モノイドの場合に同じ問いを立てれば、答えは「積を保ち単位元を保つ写像」、すなわち準同型でした。圏でも構造は同じで、条件 1 が合成可能性と合成の保存に、条件 2 が単位元の保存に対応します。

条件 2 は落とせない

条件 2 を落とすと、$\Phi(\mathrm{id}_X) = \Phi(\mathrm{id}_X\cdot\mathrm{id}_X) = \Phi(\mathrm{id}_X)\cdot\Phi(\mathrm{id}_X)$ より $\Phi(\mathrm{id}_X)$ は冪等射であることしか言えず、冪等射は一般に恒等射ではありません。

反例: $M = N = {2\times 2\ \text{実行列}}$(積についてのモノイド)とし、冪等行列 $P \neq I$ をひとつ取って $\Phi(A) = P$(定数写像)とします。すると $\Phi(AB) = P = PP = \Phi(A)\Phi(B)$ なので積は保たれますが、$\Phi(I) = P \neq I$ です。このとき空区間のクエリは、木側では $\Phi$ を通した後に $I$ を返し、配列側では $\Phi(I) = P$ を返すので別になりますね。

関手でない「積を保つ写像」たち

$\mathbf{Mat}$ 上には、一見「積を保つ」ように見えて条件 1 を満たさない写像がいくらでもあります。

• 転置 $A\mapsto A^{\mathsf{T}}$ は $(AB)^{\mathsf{T}} = B^{\mathsf{T}}A^{\mathsf{T}}$ なので、積の順序を逆にします。成分ごとに転置すると親が子の積の逆順になり、$\mathrm{Seg}_d(\mathbf{Mat})$ から出てしまいます。これは $\mathbf{Mat}^{\mathrm{op}}$ への関手であって、木の左右を反転させる操作と組み合わせない限り使えません。前々回から一貫して可換性を仮定してこなかったので、この区別は消えません。
• 行列式 は正方行列でしか乗法的でなく、そもそも $\mathrm{Mor}(\mathbf{Mat})$ 全体では定義されていません。「積を保つ」という言明が型の上で意味を持たない例です。
• サイズを揃える(ゼロ埋めして $N\times N$ にする)写像は全域で定義されますが、合成可能性を壊します。$1\times 2$ と $2\times 3$ の積は、揃えてからの積とは別物です。

これに対し $\bmod\ m$ を取る写像は関手です。対象(サイズ)を動かさず、成分ごとに $\mathbb{Z}\to\mathbb{Z}/m$ を適用するだけで、合成可能性も合成も恒等射も保ちます。前回の「値をどこかへ写してから計算してよいのは、その写像が準同型のときだけ」は、圏では「関手のときだけ」に置き換わります。

吸収元を足してモノイドに戻す

実装の立場からは、合成できない組が来たら「未定義」を表す値を返すことにして、全部モノイドとして扱ってしまうのが手軽です。

$\mathrm{Mor}(C)$ をただの集合と見て、元 $\bot$ と形式的な単位元 $e$ を追加し(恒等射 $\mathrm{id}_X$ たちは全体の単位元にはならないので、単位元は別途足す必要があります)、合成できない組の積を $\bot$ と定めれば、$\bot$ を吸収元とするモノイドが得られます。p進大好きbot 氏の記事³ では Maybe モナドの考え方として紹介されており、tatyam 氏の指摘が出典として挙げられています。

これは正しく動き、前回までの枠組みがそのまま使えますが、得られたモノイドを $M_\bot$ とすると、$\mathrm{Seg}_d(M_\bot) \cong M_\bot^{n}$ であって、右辺には型の合わない配列も入っています。本当に扱いたい $N_n(C)$ はその部分集合にすぎず、意味のある答えが返るのもそこに限られます。要するに、型検査を実行時に遅延させただけです。さきほどの空区間の話も関係していて、 $M_\bot$ 上のクエリが空区間に対して返すのは $e$ であって、$\mathrm{id}_{X_l}$ ではないです。

p進大好きbot 氏はこの点について、構造を取り替えておいて「圏が乗る」と言うのは、単位元を足しておいて「半群が乗る」と言うのと同じで不正確だ、と述べています³。この連載でやってきたことからしても、私も同じ感想で、 $M_\bot$ を載せたセグメント木の状態空間は $M_\bot^{n}$ であって $N_n(C)$ ではないという立場です。

まとめ

配列を $N_n(C)$(区間からの関手)に取り替え、直積が出てくるところをファイバー積に取り替えて、モノイドでやったことと同様のことを関手で考えました。状態空間と木の同型も、更新の移送も、値の置き換えの特徴づけも、形は変わっていません。

変わったのは配列の空間そのものです。モノイドのときは $M^n$ という何の条件もない集合が相手で、だからこそ「モノイドが載る」と言えました。圏では $\mathrm{Mor}(C)^n$ との全単射にはならず、合成可能性という追加の制約が要ります。その意味で「セグメント木に圏が載る」は言い過ぎだ、というのが私の結論で、これは先行研究の指摘³と近いですね。

作用(遅延伝播)の話も同じ枠組みで書けるはずですが、それは気力があればということで、今回はこの辺で筆を置きます。