先日, 表題に挙げた名前で文書(というよりは論文)を公開した: https://elliptic-shiho.github.io/segtree/segtree.pdf
この論文は@kimiyuki_uと私が書いたものである. 書いていたのは2019年のはじめから2021年にかけてであり, しかしその後約三年の間塩漬けとなってしまっていた. 公開にあたっての心持ちについてはPDF先頭に書いているので省略することとし, 本記事はその後読み直していて色々と思い出してきたことを書き綴っておきたい.
なお, 2024年現在における新規性の有無については未検証である. もしも研究が出ているのであれば教えてほしい.
我々の目指したかったところについて
そもそもこの論文を書く理由は(競プロ的な意味では)殆ど存在しない. 仮にこれを読んだところで新しく解けるようになる問題があるわけではないし, 確実な新規性と言えるものもない. しかしながら, 私も彼も数学の目線で競プロに関する話をしたい, なおかつ面倒な計算の嫌いな人間であった. それが執筆を始めた一つの理由である.
たとえば当時の記録によれば, 我々の間では木構造とは次のように定義されている:
$V$を集合としたとき, $\top\in V$, $P\colon V\setminus\left\lbrace\,\top\,\right\rbrace\to V$について以下が成立するならば$(V, P, \top)$を根付き木と呼ぶ.
$$ \forall v\in V\setminus\left\lbrace\,\top\,\right\rbrace.\ \exists! k\in\mathbb{N}.\ \mathrm{s.t.}\ P ^ k(v) = \top. $$
根付き木$T = (V, P, \top)$について, $v\in V$を$T$の頂点と呼び, $v\in V$を$v\in T$で略記する. また, $\top$を$T$の根と呼び, $\mathrm{root} _ T$で表す. $T$が明らかな場合には$\mathrm{root}$とすることもある. 各$v\in T$について$P ^ k(v) = \mathrm{root}$なる$k\in\mathbb{N}$は唯一つ定まることから, これを$\operatorname{depth}(v) := k$とおいて$v$の深さと呼ぶ.
$P$の逆像$P^{-1}$について, $P ^ {-1}(v)$の元を$v$の子と呼ぶ. また, $\operatorname{{Le}{af}}(T) := \left\lbrace\,v\mid v\in V, P ^ {-1}(v) = \emptyset\,\right\rbrace$の元を$T$の葉と呼ぶ. 以降, $C(v)$で$P ^ {-1}(v)$を表すものとする. $v\in V$, $k\in\mathbb{N}$について$P ^ k(v)$を$P$の祖先と呼ぶ. 明らかに$\mathrm{root}$は任意の頂点について祖先である. このことから, $v, u\in V\setminus\left\lbrace\,\mathrm{root}\,\right\rbrace$について$P ^ a(v) = P ^ b(u)$なる$a, b\in\mathbb{N}$が必ず存在し, $v$が$u$の祖先でない場合(あるいは$u$が$v$の祖先でない場合)には$P ^ {a-1}(v)\ne P ^ {b-1}(u)$が成立. この$P ^ a(v)$あるいは$P ^ b(u)$は$v, u$の最近共通祖先と呼ばれる.
このように, (病的なまでに)形式化された状態で数学の世界に競プロに頻出の概念を埋め込んでしまえば, 面倒な具体計算を減らせるし, それにある程度は自動化した議論ができるようになる. そのためには「お気持ち解説」では不足なのである1. 彼はkmyk/Jikkaにおいてその夢を(競プロ問の自動回答という形で)いくらか実現していたし, 私はデータ構造という曖昧な対象をより深く理解できるようになった.
しかしながら, セグメント木の定義そのものを研究するのはとても難易度が高かった(次節参照). そのため「セグメント木の上には代数的な構造がいろいろと"乗る"らしい」というところから「セグメント木の上に乗る代数的構造とはどのようなものか」について興味を向けたのは自然な成り行きだと言えよう. 私は, 彼が既存研究として持っていた「複数のクエリの合成を一般的にやるための十分条件」について, それを遅延伝播構造・遅延伝播積といった道具を追加定義して純数学的な立場から示した. その結果を整理・体系化したものがこの論文である.
圏への拡張の際には加群圏やモノイダル圏, 加群によって豊穣化された圏などを用いて表現できるだろうかという夢想をしていたが, 今の所それらは検討段階のままである.
セグメント木そのものについて
構造だけ見ればセグメント木はただの二分探索木である. 実際には区間クエリとの束として扱うことでセグメント木はセグメント木として扱われている. ところで, たとえば動的セグメント木の木構造は完全二分探索木としては扱われず, 単なる二分木として扱われる. セグメント木は完全二分木に限定されたデータ構造ではない にあるように, 学術的・歴史的にも平衡二分木として扱われるケースはあるようだ. いずれにせよ, 完全二分探索木の場合にのみ適用可能なテクニックはこれらにおいて通用しない.
ここまで二分木が用いられてきたわけだが, その理由が最終的に「二分探索するのがoptimal caseになるから」になることは想像に難くない. この点は事実そうなのだが, 実際には一般の木構造であっても, 適切に区間を割り振れば同様の構造を実現できる. このことから, 「セグメント木とはたんに木構造の各頂点に区間を割り当てる写像としては理解できないだろうか?」ということを考えていた.
実際, 彼は 完全二分木への添字付けであってセグメント木ではないものを考える において「添字の割り当て方」としてこの区間割当の考え方に触れている. 半年ほどの間「セグメント木とはどのような区間割当のことか, 或いは区間割当写像はいつセグメント木になるのか」について考え続けはしたのだが, 結局この点については考えがまとまらないままストールしてしまった.
セグメント木のなす空間について
管理したい列の長さを$n$としたとき, 半群$S$の乗っているセグメント木の区間操作は$S ^ n \to S ^ n$という写像だと思える. 列から列への状態遷移全てを収めてしまえば, 実際にはそのセグメント木によって表現可能な世界は一つの圏をなすのではないか. というような仮説を立てて考えていたことがある. その場合クエリは関手として取り扱われる (ことになるだろう. 完全には未証明, 検証段階のネタ).
上述定義は「セグメント木は何らかの圏として表される」という見方である. でも実際にはそれよりも面白そうな世界がある. それは「遅延伝播構造を対象, 遅延伝播構造の間の準同型を射とした圏」である. これは「遅延伝播セグメント木を対象, 遅延伝播セグメント木の間の(代数構造に関する)準同型を射とした圏」と言い換えてもよい.
本論文において示している「一定の十分条件を満たせば, セグメント木同士で直積・直和に相当する演算が可能である」という主張は, 上の圏における直和・直積の議論に言い換えられることが予想される(完全には未証明). これは「セグメント木全体からなる世界は何かしらの構造を持っていそうだ」という示唆だと思えないだろうか. セグメント木からセグメント木への射の形次第では「セグメント木同士の射が一体どのような形をしているのか」という表現論的な研究もできるだろう2.
加えて, "セグメント木全体がなす圏"が仮に$\mathbf{Sets}$や$\mathbf{Ab}$の部分圏に収まるような範囲だとすれば, そこには自然にトポス的な距離感を入れることも可能であろう. 実際のところ, 2024年現在の私が気にかかっているのはこの点, あるいはもっと引いた「セグメント木のモジュライ空間とはいかなる形をしているか」という代数幾何学的な視点である. ここまで来ると計算可能性などどうでもよくなってしまうので, その点でも彼の(あくまで計算する立場からの)助言は嬉しかったなと反復している次第だ.
最後に
セグメント木に注目して, 思い出せた範囲でこの論文に関するトピックをいくつか並べてみた. 他にもより一般の議論ができそうな箇所はあるし, 山のように存在するメモ用紙やノートを掘り返せばネタはあると思うのだが, 今思い出せないのであればそれほど考えてもいなかったことなのだろうと一旦区切ることにする. 公開できずにストールするよりも, 公開できたほうがよい.
彼の関東における住居は私の家から数駅の場所だった. その選定理由が私とこの論文に関する議論をしやすくするためだと本人に聞いた際には驚いたものだ3が, 実際そのぐらい熱を入れて書かれた作品でもある. 今となっては拙い証明も含まれているが, Twitterにおける発言の通りどうか読んでやってくれという気持ちだ.
- 実際のところ, 私がセグメント木について実務的要請から調べている際に「競プロにおける解説はどれもお気持ち解説しかない! まともな解説かと思ったらコード書いてるだけ! こんなんで一体人々はどうやってセグメント木という対象を理解・勉強してるんだ?」とキレて彼に質問した際に「それはまともな定義がそもそも存在しないからですよ」と返ってきたのが本研究の端緒である. なお, 目的が違うがためにこのような感想になっているだけで, お気持ち解説自体を批判する意図はない.↩
- 計算量とセットで考えなければならない計算機科学の文脈においては, 線形演算が如く 「小さい演算」の形式的定義 をwell-definedに定義してやらなければならない可能性は実際に高い.↩
- 普段からの交流もしやすくなったのはとてもよかった. たとえば mod で計算するときに零の重複度も持つテク は私が暇だからと彼を呼びつけたコメダでの議論が元になっている. リモート勤務全盛の今言うのも何だが, オフラインでの自由度の高さは生産性に無視できない影響を与えることを実感した.↩
