TL;DR

SegmentTreeはモノイドが扱えるデータ構造だという理解をしていたが、モノイドではなく半群を扱えるデータ構造だと理解した方が良いのではないかと考えている。

前提知識

半群とモノイドについて

まず半群とモノイドについて整理する。

半群

結合法則を満たす群構造のことを半群と呼ぶ。結合法則とは、任意の群の要素 $a$ 、 $b$ 、 $c$ について

$\begin{eqnarray} (a \circ b) \circ c = a \circ (b \circ c) \end{eqnarray}$

が成立することを言う。

モノイド

結合法則を満たしかつ単位元が存在する群構造のことをモノイドと呼ぶ。ある群の要素 $e$ とは単位元であるとは、任意の群の要素 $a$ について

$\begin{eqnarray} a \circ e = e \circ a = a \end{eqnarray}$

が成立することを言う。

すなわち、モノイドと半群の違いは単位元が存在するかどうかである。

SegmentTreeについて

AC libraryによると

モノイド、つまり
- 結合律
- 単位元の存在
を満たす代数構造に対し使用できるデータ構造です。
長さNのSの配列に対し、
- 要素の1点変更
- 区間の要素の総積の取得
をO(logN) で行うことが出来ます。

と説明されている。コンストラクタは2種類あり、 a. 群の集合、要素間の演算、単位元、SegmentTreeサイズ b. 群の集合、要素間の演算、単位元、初期配列

の2つの与え方がある。

背景

ABC254-F問題をやっていた時に、正の整数列のある区間の最大公約数を高速で求めるためにSegmentTreeが使えないか検討していた。そのとき、SegmentTreeを使う条件として結合則の成立と単位元の存在が要求されるが、結合則の成立は問題なさそうだが、単位元については少し手が止まった。数学的には、あらゆる正の整数を掛け合わせたものすごい大きい整数をが単位元になりそうだが、実装する上ではoverflowが起きてしまうのでそのような単位元は実装上は使えない。そこで、0をそのものすごく大きい数の代用に使おうと考えていたが、ここでふと「あれ、単位元の定義がなぜ必要なのか」と思い始めた。0を単位元として定義するにしても、正の整数列の区間取得を行う限りにおいては0が登場することはなく、なぜ「0を単位元にします」という宣言を実装しないといけないのか疑問に感じ、SegmentTreeのデータ構造の一般性を失わないために、「SegmentTreeは半群に対して使えるデータ構造」という理解をした方がよいのではないかと考えた。

SegmentTreeに単位元を与える必要があるか

SegmentTreeの実装において単位元は次の2ケースで使われるようである。

Treeノードの初期値
区間取得を行うときの区間値の初期設定値

1.について、ノードをどの値で初期化することに関してはユーザーの責務とする考え方も自然に感じる。単位元で初期化することにより部分的にノードの値が更新されたときにも区間取得クエリが正しく動くため便利という考え方もあるかもしれないが、部分的にノードの値を更新するような操作を許さず、初期化されていないノードを含む区間取得クエリに対しては返す値を保証しない（未定義動作）ということでも良いのではないか。

2.について、これは完全に実装をシンプルにするためだけの都合なので、それを理由にユーザーに単位元を要求してほしくない。

以上から、一般的に「SegmentTreeは半群を扱えるデータ構造」という理解をしたい。ただし、あるライブラリが実装の都合で単位元を要求しその結果として「このSegmentTreeはモノイドを扱えるデータ構造」というように使い方を限定すること自体は問題ないと思っている。