SegmentTreeに載る代数的構造について - Qiita

概要 実装が一通り分かってる人向けです。ライブラリを再整備していたらここらへんをまとめたくなったので。 普通のセグ木にモノイドが載るという話は掃いて捨てるほどあるので、やりたいのは主に後の2つです。 2024/02/12 追記 この記事は、SegmentTree に乗る構造に対する曖昧な理解を数学的な言葉を用いて言語化することで理解を深めることを目的に書かれたものです。そのため内容に関して厳密に議論されているとは言い難く、言葉遣いに関しても怪しいところが多いものになっていると思われます。 本記事はこのような欠点を抱えていながら著者の力不足により改稿できていませんでしたが、kimiyuki さんと Shiho Midorikawa さんによる厳密な議論が以下のPDFにて公開されています。このようなことを書くのは他人の努力にただ乗りするようで不誠実でありますが、数学的な議論にある程度慣れている