salpik https://blog.hatena.ne.jp/salpik/ salpikのブログ https://salpik.hatenablog.com/ TL;DR SegmentTreeはモノイドが扱えるデータ構造だという理解をしていたが、モノイドではなく半群を扱えるデータ構造だと理解した方が良いのではないかと考えている。 前提知識 半群とモノイドについて まず半群とモノイドについて整理する。 半群 結合法則を満たす群構造のことを半群と呼ぶ。結合法則とは、任意の群の要素、、について が成立することを言う。 モノイド 結合法則を満たしかつ単位元が存在する群構造のことをモノイドと呼ぶ。ある群の要素とは単位元であるとは、任意の群の要素について が成立することを言う。 すなわち、モノイドと半群の違いは単位元が存在するかどうかである。 SegmentT… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fsalpik.hatenablog.com%2Fentry%2F2024%2F03%2F03%2F150510" title="SegmentTreeはモノイドを扱えるデータ構造という話について - salpikのブログ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2024-03-03 15:05:10 rich https://salpik.hatenablog.com/entry/2024/03/03/150510 1.0 100%