趣旨

競技プログラミングではセグメント木と呼ばれるデータ構造（数列などの要素の管理方法を工夫することで様々な処理を高速に実現できるようにしたもの）が使われます。セグメント木は数列より広く、モノイドという代数構造が乗る（つまりモノイドに値を持つ配列を管理できる）のですが、圏はモノイドを更に一般化した概念です。それではセグメント木と圏にはどのような関係があるでしょう？

どうも出典[1]の$\S$ 6.3に「モノイドや半群と比べて, 圏はセグメント木と関連する構造をより過不足なく捉えられていると言える.」と述べられていることを踏まえてなのか競技プログラミング界隈では「セグメント木にはモノイドより広く圏が乗る」的な言説を述べることがあります。しかし[1]の元々の主張は恐らくあくまで厳密な意味を知っている人向けの標語的なものに過ぎず、圏そのものはモノイドと同様に「無条件には」乗りません。

この記事では[1]の正確な意味を説明するとともに、セグメント木の基本的な知識を持っている競技プログラマー向けに何故「セグメント木には圏が乗る」という言説が文字通りには誤りであるかを説明します。

ただし筆者（$p$進大好きbot）はセグメント木についてはほとんど素botであるため、何か間違えているかもしれません。その場合はご一報くださいますと幸いです。

結論

結論から言うと、「セグメント木に乗るのは区間から圏への関手」という表現がより正確です。

そのことを説明するために、そもそも「モノイドが乗る」とはどういう意味かに戻って説明する必要があります。

なお、上で述べている圏とは小圏のことです。小圏（small category）は圏の中でも特別なものなのですが、小圏のみを指す文脈でも圏（category）と呼ぶ慣習がある（その場合は小圏でない圏をbig categoryと呼ぶ）ためにそのようにしています。

例えば競技プログラミングでもおなじみの種の理論では小圏でない圏$\mathbb{B}$を使います。これは亜群と呼ばれる特別な小圏で、モノイドではありません。

他にも競技プログラミングでおなじみのマトロイドと関係の深い単体的集合は、小圏$\Delta$から小圏でない圏$\textrm{Set}$への反変関手を使います。これらもモノイドではありません。

以下では混乱を避けるため、（[1]などの引用に関わる部分を除いて）きちんと圏と小圏を区別して説明します。

小圏の定義

小圏にはいくつかの等価な定義があるのですが、ここでは競技プログラマーに分かりやすいと思われる定式化の１つを説明します。

小圏とは、以下のデータの組み合わせ$(M,s,t,\circ)$に後述する要件を課したものです。

1. 集合$M$
2. $2$つの写像 $s,t \colon M \to M$
3. 写像$\circ \colon M^{[2]} \to M$（ただしここで$M^{[2]} := \{(m_0,m_1) \in M^2 \mid s(m_0) = t(m_1)\}$と置いた）

$M$の要素を射と呼び、写像$\circ$を合成と呼びます。ただし$M^{[2]}$は$M^2$より小さくなり得るので、合成は$M^2$全体で定義されるとは限りません。

$s$の像$\{s(m) \mid m \in M\}$を$V$と置き、差集合$M \setminus V$を$E$と置きます。小圏に課される要件は以下の4つです。

1. $t$の像$\{t(m) \mid m \in M\}$は$V$と等しい。
2. いかなる$v \in V$に対しても$s(v) = v = t(v)$である。
3. いかなる$(m_0,m_1) \in M^{[2]}$に対しても$s(m_0 \circ m_1) = s(m_1)$かつ$t(m_0 \circ m_1) = t(m_0)$である。
4. （単位律）いかなる$m \in M$に対しても$m \circ s(m) = m = t(m) \circ m$である。
5. （結合律）いかなる$(m_0,m_1,m_2) \in M^{[3]}$に対しても$m_0 \circ (m_1 \circ m_2) = (m_0 \circ m_1) \circ m_2$である。（ただしここで$M^{[3]} := \{(m_0,m_1,m_2) \in M^3 \mid s(m_0) = t(m_1) \land s(m_1) \in t(m_2)\}$と置いた）

これだけではあまりイメージがつきにくいと思うので、代数的な説明と幾何的な説明をします。

代数的な説明

代数が得意な人向けにイメージを説明します。$M$は$2$項演算のようなものが定義されているのですが、普通の$2$項演算と違って定義域に制限があります。

各$m \in E$ごとに$t(m)$と$s(m)$が$m$にとっての左単位元と右単位元のような機能を持ちます。特に$s(m) = t(m)$となる時は$s(m)$が単位元の役割を持ち、そのように表せる射を恒等射と呼ばれます。

普通のマグマであれば単位元は一意ですが、$2$項演算の定義域に制限があるため恒等射はまるで一意ではなく、$V$が恒等射全体の集合となります。

恒等射$v \in V$を１つ固定するごとに、$v$を単位元に持つモノイドが$M$の部分集合として排他的に取れ、それらを集めると$s(m) = t(m)$を満たす$m \in M$全体の集合となります。

それらのモノイドのいずれにも属さない要素たち（$s(m) \neq t(m)$となる$m \in M$たち）がまだまだ存在するかもしれず、それらがモノイドたちを結ぶおかげ様々な性質が現れます。

幾何的な説明

グラフ理論が得意な人向けにイメージを説明します。$V$を頂点集合として$E$を辺集合とする有向グラフを考えましょう。具体的には各$m \in E$を$s(m)$から$t(m)$へ至る有向辺とみなせば良いです。

この有向グラフは多重辺を持ち得ますが、自己ループを持ちません。むしろ各$v \in V$が自己ループのようなもので、それらを潰して頂点と同一視することで自己ループがなくなっていると考えても良いです。

有向辺には合成演算が定義されています。有向辺$m_0$と$m_1$が逆順に（$m_1$を通ってから$m_0$を通る順に）結合できる場合にのみ、結合結果と同じ頂点を結ぶ有向辺$m_0 \circ m_1$が定義されます。

合成には色々な解釈がありえて、例えば合成演算を「$2$つの有向辺$m_0$と$m_1$を逆順に続けて通る代わりに別の特定の有向辺$m_0 \circ m_1$を通って良い」という経路の簡約化に関するルールの集まりだと思ってもよいです。

モノイドとの関係

小圏の例はモノイドで与えられます。具体的には、モノイド$M$の下部構造としての集合もまた$M$と書き表すことにして、$M$の単位元$e$に値を取る定数写像$M \to M, m \mapsto e$を$c$と置いて、$M$の演算を$\circ$と置くと、$(M,c,c,\circ)$が小圏となります。この小圏は$V = \{e\}$特に$\lvert V \rvert = 1$を満たします。ここで$\lvert V \rvert$は$V$の濃度（要素数）です。

ところで小圏にも群やモノイドと同様に同型という概念があります。一般に与えられた小圏$(M,s,t,\circ)$が追加の条件$\lvert V \rvert = 1$を満たす時は上の方法でモノイドから作る小圏と同型になります。そのため、$\lvert V \rvert = 1$を満たす小圏のこともモノイドと呼びます。

この意味で、小圏は確かにモノイドの一般化とみなすことができます。

小圏の例

モノイド以外に競技プログラミングで現れるかもしれない小圏の例を紹介します。

写像の小圏

$V$を集合族とし、各$(v_0,v_1) \in V$に対し$\textrm{Hom}(v_0,v_1)$で写像$v_0 \to v_1$全体の集合を表すとします。

$(v_0,v_1) \in V$をわたる$\textrm{Hom}(v_0,v_1)$の排他的和集合を$M$と置きます。

この時各$v \in V$に対し恒等写像$\textrm{id}_v \colon v \to v$を対応させることで単射$V \hookrightarrow M$が得られ、$V$をこの像と同一視します（つまり像もまた記号を濫用して$V$と書きます）。

各$m \in M$は$V$の要素を定義域と終域に持つ写像なので、定義域を取り出す写像$s \colon M \to V \subset M$と終域を取り出す写像$t \colon M \to V \subset M$が定まります。

すると組$(M,s,t,\circ)$は小圏をなします。ここで$\circ$は写像を合成する演算です。

線形写像の小圏

$K$を体とし、$V$を$K$線形空間の族とし、各$(v_0,v_1) \in V$に対し$\textrm{Hom}_K(v_0,v_1)$で$K$線形写像$v_0 \to v_1$全体の集合を表すとします。

$(v_0,v_1) \in V$をわたる$\textrm{Hom}_K(v_0,v_1)$の排他的和集合を$M$と置きます。

この時各$v \in V$に対し恒等写像$\textrm{id}_v \colon v \to v$を対応させることで単射$V \hookrightarrow M$が得られ、$V$をこの像と同一視します（つまり像もまた記号を濫用して$V$と書きます）。

各$m \in M$は$V$の要素を定義域と終域に持つ線形写像なので、定義域を取り出す写像$s \colon M \to V \subset M$と終域を取り出す写像$t \colon M \to V \subset M$が定まります。

すると組$(M,s,t,\circ)$は小圏をなします。ここで$\circ$は線形写像を合成する演算です。特に各$K$線形空間が有限次元なら、$\circ$は（正方行列とは限らない）行列の積に翻訳されます。

道の小圏

$G$を（自己ループも多重辺も持って良い）有向グラフとし、その頂点集合を$V$と置きます。各$(v_0,v_1) \in V$に対し$P_G(v_0,v_1)$で$v_0$から$v_1$へ至る$G$の道（ただし$v_0 = v_1$の時は空な道を許す）全体の集合を表すとします。

$(v_0,v_1) \in V$をわたる$P_G(v_0,v_1)$の排他的和集合を$M$と置きます。

この時各$v \in V$に対し$v$から$v$へ至る空な道を対応させることで単射$V \hookrightarrow M$が得られ、$V$をこの像と同一視します（つまり像もまた記号を濫用して$V$と書きます）。

各$m \in M$は$V$の要素を始端と終端に持つ道なので、始端を取り出す写像$s \colon M \to V \subset M$と終端を取り出す写像$t \colon M \to V \subset M$が定まります。

すると組$(M,s,t,\circ)$は小圏をなします。ここで$\circ$は道を逆順に結合する演算です。

半順序集合

組$(V,E)$が（狭義）半順序集合であるとは、$E$が$V^2$の部分集合であって以下を満たすということです

1. （非反射律）いかなる$v \in V$に対しても、$v E v$でない。
2. （反対称律）いかなる$(v_0,v_1) \in V^2$に対しても、$v_0 E v_1$でないまたは$v_1 E v_0$でない。
3. （推移律）いかなる$(v_0,v_1,v_2) \in V^3$に対しても$v_0 E v_1$かつ$v_1 E v_2$ならば$v_0 E v_2$である。

ただしここで、$(v_0,v_1) \in V^2$に対する$v_0 E v_1$は$(v_0,v_1) \in E$の略記です。この記法により結果的に$E$は$v_0 E v_1$を満たす$(v_0,v_1) \in V^2$全体の集合と一致するため$E$をこの半順序集合のグラフとも呼びます。

例えば集合$S$が与えられている時、$V$を$S$の部分集合全体の集合として、$E$を真部分集合関係とすると、$(V,E)$は半順序となります。

$(V,E)$を半順序集合とします。$V$と$E$の排他的和集合を$M$と置き、恒等写像$V \to V$と第$1$成分を取り出す写像$E \to V$の合併$M \to V \subset M$を$s$と置き、恒等写像$V \to V$と第$2$成分を取り出す写像$E \to V$の合併$M \to V \subset M$を$t$と置き、写像$M^{[2]} \to M, \ (m_0,m_1) \mapsto (s(m_1),t(m_0))$を$\circ$と置きます。

ここで$M^{[2]}$は$s$と$t$から定めたもので、その要素は$s(m_0) = t(m_1)$を満たす$(m_0,m_1) \in E^2$であり、$(m_0,m_1) = ((s(m_0),t(m_0)),(s(m_1),t(m_1)))$と表せることに注意しましょう。つまり$\circ$は$s(m_0) = t(m_1)$部分を消して新たな組を作るもので、推移律そのものを体現する演算です。

すると$(M,s,t,\circ)$は小圏をなします。そしてこの小圏は有向グラフとして多重辺を持ちません。

一般に与えられた小圏$(M,s,t,\circ)$が追加の条件「有向グラフとして多重辺を持たない」を満たす時は上の方法で半順序集合から作る小圏と同型になります。そのため、条件「有向グラフとして多重辺を持たない」を満たす小圏のことも半順序集合と呼びます。

この意味で、小圏は半順序集合の一般化とみなすことができます。

セグメント木に小圏が乗らないこと

そもそも「セグメント木にモノイドが乗る」とは、「セグメント木によってモノイドの要素からなる任意の固定長配列が管理できる（それにより総和が高速に計算できる）」ということです。

同じ要領で「セグメント木に小圏が乗る」でしょうか？　モノイドと小圏の関係を考えると、「セグメント木に小圏が乗る」という主張は、「セグメント木によって小圏の射からなる任意の固定長配列が管理できる（それにより合成が高速に計算できる）」ということです。

しかしながらセグメント木はその特性上、配列で隣り合う成分同士に合成が定義されなければ機能しません。

従ってセグメント木にモノイドが乗ることと同じ要領ではセグメント木に小圏が乗らないわけです。

言外に配列に条件を課すことを許して「（隣り合う成分同士に合成が定義されれば乗るから）小圏も乗る！」と豪語する人もいるかも知れませんが、それは「（成分の生成する部分マグマが結合律を満たせば乗るから）マグマも乗る！」と豪語することと同レベルの詭弁です。

マグマがセグメント木に乗ると聞けば誤った言説だと判断するのが普通であり、それと同様に小圏がセグメント木に乗るという表現は誤ったものです。

ただし以前maspyさんが「モノイドがのるとされる文脈の一般化であれば（適切な）圏がのるという表現でよいです」とご説明なさっていたため、もしかしたら上級者には有名な手法であって配列で隣り合う成分同士に合成が定義されなくても「構造を変更したりせずに」セグメント木を機能させる方法があるのかもしれません（後述するように、構造を好きに変えてもよいのであればいくらでも乗ります）。「適切な」と注意書きがあるのも気になります。一般の圏によっては乗らないということが含意されているようなので、関手による定式化より狭い範囲でしか適用できないのかもしれません。正確な条件付けが知りたいところですがこの辺は筆者の勉強不足で推測できませんでした。

ただその前に合成が関手でないことを気にしていらしたりしていた^[2]ので、何かしら特殊な流儀を採用しているだけかもしれません。念のためにこちらとこちらでご質問させていただきましたが、特にご返信もございませんので真意は分かっておりません。

セグメント木に実際に乗るもの

上で見たように、「セグメント木にモノイドが乗る」という表現をする時の「モノイド」部分を直接広い代数構造に置き換えることはできません。

また「セグメント木にモノイドの要素からなる任意の固定長の配列が乗る」という表現をするときの「モノイド」部分を直接広い代数構造に置き換えることはできません。

一方で「モノイドの要素からなる任意の固定長の配列が乗る」部分を「小圏の射からなる任意の固定長配列であって隣接成分が合成可能なもの」に置き換えることは正しいです。

恐らくこれが[1]の意図するところでしょう。標語的に表現を縮めた結果として必要な条件を落としてしまい初学者に誤解を広めてしまうことを避けるには、上のような正確な表現をすべきです。

とはいえこの表現は長いです。もう少し短くしたいですよね。そこで役立つのが「区間からの関手」です。

$N$を非負整数として、全順序集合$\mathbb{Z} \cap [0,N)$は狭義プログラミングの文脈ではしばしば$[0,N)$と略記され区間という用語が濫用されます。

全順序集合は半順序集合の特別なものなので小圏をなすわけなので区間も小圏です。

また群にとっての群準同型やモノイドにとってのモノイド準同型と同様、小圏にも準同型の概念が定義されて関手と呼ばれています。

小圏がモノイドの一般化であったことと整合的な見方で、関手はモノイド準同型の一般化となります。

一般の関手の定義はさておき、小圏$(M,s,t,\circ)$が与えられた時に区間$[0,N)$から$(M,s,t,\circ)$への関手を与えることと、$M$の射からなる長さ$N$の配列であって隣接する成分がその順に合成可能なものを与えることは等価です。

以上より、セグメント木に実際に乗るものは小圏そのものではなく、区間から小圏への関手です。もちろん区間から小圏への関手やそれと等価なものが乗ることを指して「圏が乗る」と表現している人が多いのかもしれませんが、先述したように「モノイドが乗る」という表現の意味を考えると「小圏が乗る」という表現のそのような正当化は詭弁であり、「区間から小圏への関手が乗る」がより正確な表現となるということです。

文字通りに受け取ると誤りな標語は初学者を誤解させやすいので、なるべく正確な表現を心掛けていきたいものですね。

なお「区間から小圏への関手が乗る」という定式化の利点の１つは、和集合を演算として端点情報付きの半開区間の列$([0,1),[1,2),\ldots,[N-1,N))$がセグメント木に乗ることが即座に分かることです。区間$[0,N)$の射の列$((0,1),(1,2),\ldots,(N-1,N))$に翻訳すれば恒等関手を考えるだけですからね。ここで「端点情報付きの」と言っているのは、集合としては単なる空集合である半開区間$[0,0)$と$[1,1)$などを区別するためです。道の小圏を考える時に空の道にも始端と終端の情報があったことと同じです。

この他にも関手が（広義の半順序に対する）順序保存写像の一般化であることを踏まえれば、上記の区間列の端点$(0,1,2,\ldots,N)$を一般の広義単調増大列に置き換えたものもセグメント木に載ることが即座に分かります。

圏と関手の枠組みで抽象化して捉えることで、様々な既存の概念が議論に流用できてad hoc性が減るわけですね。上級者と違って色んな考察に詰まりやすい筆者にとって、抽象化でad hocな議論が減ることは嬉しいことです。

遅延評価

ところで皆さんは、「セグメント木で範囲更新の遅延評価ができるのはどういう時か？」と問われたらどう答えますか？

必要十分条件を与えることは困難なので、実用上満足の行く十分条件を与えたいものです。

基点つきマグマからモノイドへの作用

そもそもモノイドを乗せた場合にすらある程度冗長な条件を除いた十分条件は競技プログラミング界隈ではあまり有名ではなさそうです。

というのもAtCoder Libraryのドキュメントをはじめとする遅延セグメント木の解説ではかなり緩めの十分条件が与えられているだけだからです。

例えば「基点付きマグマからモノイドへの作用であって基点を恒等写像に移すものが与えられた時」レベルで冗長な条件を除いた解説を読んだことがありません。

しかしこの十分条件すら実用上満足の行くものではなく、例えば区間代入や区間加算も遅延評価できる範囲更新ですがモノイド側を変更しないと基点付きマグマからモノイドへの作用には必ずしも翻訳できません。

区間代入と区間加算を許容するような自然な十分条件はなかなか言い表しにくそうです。

基点つきマグマから小圏への作用

さて、モノイドの要素からなる固定長の配列を一般化して、区間から小圏$C$への関手を乗せた場合はどうでしょう？

なおさら競技プログラミング界隈ではある程度冗長な条件を除いたものが有名じゃないだろうと予想します。

答えるなら、例えば「基点付きマグマから$C$への作用であって単位元を恒等関手に写し恒等射を保つもの」が１つです。

また一般の範囲更新ではなく全体更新しか考えない場合だと「恒等射を保つ」という条件は不要になります。「恒等射を保つ」は作用が自動的に満たす「恒等射を恒等射に写す」より強い条件であることに注意しましょう。

例えばセグメント木に区間から線形写像の小圏への関手を乗せる場合、恒等射を保つという条件が外れると作用によって各ベクトル空間の次元すら変わりうる（もちろんコンパイル時にも固定できない）ものすら許容されるということです。

しかしやはり範囲更新のこの十分条件も区間代入や区間加算をカバーしていません。そこで、もう少し汎用性の高い十分条件を与えましょう。

基点つきマグマから区間から小圏への作用モノイドへの準同型

ここからは圏論にある程度詳しい人向けの説明として、圏論の記法と用語を断りなく用います。まず小圏$C$が与えられているとします。

ここだけの用語で自己写像$F \in \textrm{End}(\textrm{Hom}_C)$が$C$の自己変換であることを以下の2条件を満たすこととして定義します。

1. 任意の$v \in \textrm{Ob}(C)$に対し、$g(\textrm{id}_v) = \textrm{id}_v$である。
2. 任意の$(v_0,v_1) \in \textrm{Ob}(C)^2$と$m \in \textrm{Hom}_C(v_0,v_1)$に対し、$g(m) \in \textrm{Hom}_C(v_0,v_1)$である。

これは対象を保つ自己関手にも似ていますが、関手性（合成の整合性）は課されていないことに注意しましょう。

$C$の自己変換全体の集合を$\textrm{Trans}(C)$と置きます。$\textrm{Trans}(C)$は$\textrm{End}(\textrm{Hom}_C)$の部分モノイドとなります。

次に小圏$I$が与えられているとします。ここだけの用語で$I$から$C$への作用とは、写像$F \colon \textrm{Hom}_I \to \textrm{Trans}(C)$であって任意の$(\ell_0,\ell_1) \in \textrm{Hom}_I^{[2]}$と$(m_0,m_1) \in \textrm{Hom}_C^{[2]}$に対し以下を満たすもののこととします。

• $F(\ell_0)(m_0) \circ F(\ell_1)(m_1) = F(\ell_0 \circ \ell_1)(m_0 \circ m_1)$

この条件は、$F$をカリー化した時に$I \times C$からの関手となることと同値です。つまり$I$から$C$への作用は関手$I \times C \to C$に追加の条件（$C$の自己変換を定めること）を課したものとなります。

なお合成に関するこの条件は、$I$から$C$の自己関手圏への関手と合成を見る方向が違う（関手の合成方向ではなく射の合成方向を見る）ことに注意してください。

$I$から$C$への作用全体の集合を$\textrm{Act}(I,C)$と置きます。$\textrm{Act}(I,C)$は直積モノイド$\textrm{Trans}(C)^{\textrm{Hom}_I}$の部分モノイドとなります。

このように小圏から小圏への作用のモノイドを定式化すると、セグメント木の範囲更新が遅延評価できるための十分条件が得られます。

セグメント木に区間$[0,N)$から$C$への関手を乗せるとします。例えば「基点つきマグマから$\textrm{Act}([0,N),C)$への準同型であって基点を単位元に写すものが与えられた時」、それによる範囲更新は遅延評価が可能です。

これならば基点つきマグマから小圏への作用であって単位元を恒等関手に写し恒等射を保つものも、区間代入も、区間加算も、区間等差数列加算もカバーしています。実用上はそれなりに満足行く十分条件ではないでしょうか？

もちろんどのような理解が分かりやすいかは人それぞれですが、ad hocな議論をなくせばなくすほど納得しやすい（先人の知恵として受け入れるしかないのではなく自力で一本の道筋が見えるほど理解できるようになる）という方は、ここまでとはいかずともある程度抽象化した考え方がおすすめです。（恥ずかしながら問題をあまり解けない筆者がおすすめをするのは説得力に欠けるのですが、問題をあまり解けないなりの工夫として同じレベルの方々におすすめという意味です）

実際筆者自身の体験として、元々は「先人の知恵として長さを持たせたら何故かうまくいくことが証明できた」という程度の満足度の低い体験しか得られておらず、モノイドを変えなければならないのは作用の定式化がおかしいのではないかという疑念がつきまとっており、そのせいでセグメント木にかなりの苦手意識を持っていました。一方でこちらで圏と関手を用いたセグメント木の定式化に自力で気づけた時、初めて区間代入や区間加算ができることに納得できました。

Maybeモナド

ところで集合$M$と$M^2$の部分集合$D$と写像$\circ \colon D \to M$が与えられた時、実装上は$\circ$を$M^2$全体で定義されているものとして扱いたいことが多々あります。

そこで役に立つのがMaybeモナドの考え方で、$M$に属さない項$x$を１個$M$に追加したものを$M_+$と置き、新たな写像$\circ_+ \colon M_+^2 \to M_+, (m_0,m_1) \mapsto m_0 \circ_+ m_1$を

• $(m_0,m_1) \in D$ならば$m_0 \circ_+ m_1 = m_0 \circ m_1$
• $(m_0,m_1) \notin D$ならば$m_0 \circ_+ m_1 = x$

と定めることで$(M,\circ)$を拡張したマグマ$(M_+,\circ_+)$を得ることができます。例えば小圏に対しこの方法で得られるマグマは$x$を吸収元とするモノイドとなるので、このままセグメント木に乗せることができることが知られています^[3]。

ただしこの方法で吸収元つきモノイドに翻訳した場合、遅延評価で混乱しないように注意する必要があります。

というのも、区間から小圏への関手を乗せた場合の遅延評価の要件は、吸収元つきモノイドを乗せた場合の遅延評価の要件と異なるからです。

後者の十分条件は基点つきマグマからモノイドへの作用であって基点を恒等写像に写すものが全て許されますが、その中でも前者の十分条件に対応するものはごく一部の限られたものですし、前者の十分条件でカバーできていた区間代入や区間加算などが後者の十分条件ではカバーされなくなります。

吸収元を追加した分下部集合が大きくなり$s$と$t$の情報も失うので、遅延評価の要件も同値でないものに変わってしまうというわけですね。

実用上は単に制約が緩まるだけであるなら実害がありませんが、本来考えない範囲更新まで含めた議論になってしまい混乱しやすいのと、実際には本来考えたい区間代入や区間加算もカバーしていない十分条件になることに注意しましょう。

また吸収元つきモノイドに拡張しておけば、区間から小圏への関手と違って隣り合う成分同士が合成可能でないケースも扱うことができます。

ただ代数構造を拡張することは代数構造を変更することにほかならないので、それをもって「隣り合う成分同士が合成可能でなくても小圏が乗る」という言い方は不正確なのでやめたほうが良いです。

例えばセグメント木に半群が乗るかと言われれば、単位元を追加すれば乗るという意味では乗りますがそれは結局単位元をつけて構造を変えた、別のモノイドを乗せていることに他なりません。

極端な話、セグメント木にマグマが乗るかと言われた時にマグマ構造を全く別物のモノイド構造に取り替える（例えば部分モノイドに取り替えてたり、それどころか商モノイドなどに取り替えてして元のマグマ構造に関する総和と別物な値を管理する）ことを指して「マグマが乗る」と言ったりしないことと同様です。

その他のデータ構造

何もセグメント木が特別なわけではなく、平方分割でも区間から小圏への関手が乗ります。ただ平方分割はこれで限界というわけではなく、例えば集合$X$と自由アーベル群$\mathbb{Z}^{\oplus X}$（もしくは自由モノイド$\mathbb{N}^{\oplus X}$）の組を乗せることができ、単に自由アーベル群や自由モノイドを乗せる場合と比べて計算量が削減できます。

累積和も区間から亜群への関手を乗せられますね。通常の実装では可換性が必要なフェニック木には亜群だと困りますが、フェニック木を２本使う区間加算フェニック木もフェニック木として扱うことと２本使えばモノイドが乗ることから同じ要領で区間から小圏への関手も乗ると言っても許されそうです。

出典

1. Kimiyuki Onaka and Shiho Midorikawa, セグメント木と代数構造の理論, 2024-02-12.
2. maspy (maspy_stars), 少なくとも「合併に対応する処理が～～関手になっている」は誤りではないですか？　圏論定式化なら op() は射の合成であって、op() は関手ではない気がする。どう認識しているのだろう。, twiter, 2024-08-04.
3. tatyam (tatyam_prime), “計算不能” を集合に入れてしまえばモノイドになってしまうという話は，ある, twitter, 2024-05-15.