前置き
この記事は公立はこだて未来大学 Advent Calendar 2020 https://adventar.org/calendars/5150
の14日目の記事です。
遅延評価セグメント木の抽象化の部分で詰まったので記事を残しておこうと思いました。
本題
遅延評価セグメント木に載せられるのは作用付きモノイドです。
作用付きモノイドとは
モノイド(X,〇,ex), (M,★,em)と□: X□M→Xが成り立つ二項演算□について
- Xの任意の元xについて x□em = x
- Xの任意の元x1, x2,Mの任意の元mについて (x1〇x2)★m = (x1★m) 〇 (x2★m)
- Xの任意の元x,Mの任意の元m1, m2について (x□m1) □ m2 = x □ (m1□m2) を満たしているものです。
モノイド(X,★,e)とは集合XとXの二項演算★: X × X → Xについて
- 結合律
- 単位元eを持つ
を満たしている代数的構造です。★: X × X → Xとは、Xの任意の元a,bについてa★bもXの元であるということです。
遅延評価セグメント木に対して、
(X,〇,ex)は区間取得の部分、(M,★,em)は区間更新を貯める部分、□: X□M→Xは区間更新を貯めている配列を元の配列に作用させる部分に対応しています。
最後に
時間が無くかなり雑になってしまいました。自分の中で分かったつもりになっているものも、言葉できちんと説明するのは難しいですね。
遅延評価セグメント木についてもっと詳しく知りたい方はreferenceの記事を読むといいかなと思います。
Reference
セグメント木を徹底解説！0から遅延評価やモノイドまで
https://algo-logic.info/segment-tree/
Wikipedia モノイド
https://ja.wikipedia.org/wiki/%E3%83%A2%E3%83%8E%E3%82%A4%E3%83%89#%E3%83%A2%E3%83%8E%E3%82%A4%E3%83%89%E4%BD%9C%E7%94%A8%E3%81%A8%E4%BD%9C%E7%94%A8%E7%B4%A0%E3%83%A2%E3%83%8E%E3%82%A4%E3%83%89
ACL Beginner Contest解説
https://www.youtube.com/watch?v=D0Op33UL_cA&feature=youtu.be 1:19:22~
遅延評価セグメント木をソラで書きたいあなたに
https://tsutaj.hatenablog.com/entry/2017/03/30/224339