この記事は、Competitive Programming Advent Calendar 2016 - Adventarの15日目の記事です。
この記事について
去年(2015年)の12月ごろ、「セグメント木が任意のモノイドに対して使えるという(当たり前のことが)明示的に書かれた日本語の記事がないなぁ」と思い、「(当時)来年のAdvent Calendarあたりに書こうか」と思ったので書きました。その後調べてみましたが、どうやらこの1年(2015年12月-2016年12月)で割と書かれたようでした。(この記事の意味とは…)
前述のように多数の記事がこの1年間で出たので、この記事は主にそれらへのリンクを貼り、場合によってコードを紹介することにします。
データ構造と代数構造
セグメント木 <=> モノイド
集合M、Mの要素eとその上の二項演算*があり、*が
- e * x = x * e = x *1
- x * (y * z) = (x * y) * z
が成立する場合、(M, e, *)はモノイドであるという。
モノイド(M, e, *)に対して、セグメント木というデータ構造で、Mの元からなる配列を表現できる。このデータ構造は構築がO(n)ででき、1要素の更新と区間に対する*の演算(区間和*2 )がO(log(n) )でできる。(nは配列の長さ)
詳しくはここをみてください:
qiita.com
qiita.com
BIT <=> アーベル群
(先頭からの累積和を計算するだけなら可換モノイド(= アーベル群 - 逆元 = モノイド + 可換律)でよい)
セグメント木と同じく構築O(n)、1要素の更新と区間和がO(log(n))でできる。
アーベル群の上の累積和を使う問題: 蟻本をみてください。その他自分が解いた問題の中で:
C: データ構造 - AtCoder Regular Contest 033 | AtCoder
C: 転倒距離 - AtCoder Regular Contest 043 | AtCoder
No.449 ゆきこーだーの雨と雪 (4) - yukicoder
遅延セグメント木 <=> 作用付きモノイド
データ構造と代数(後編) · tomcatowl's blogに詳しく書いてあるので、参照されたい。
サンプルコード
バグっているのしかないので掲載できません…(>_<)
SparseTable <=> 交叉半束(meet-semilattice)
集合Aとその上の二項演算/\があり、それが
- idempotency (べき等律) a /\ a = a
- commutativity (可換律) a /\ b = b /\ a
- associativity (結合律) a /\ (b /\ c) = (a /\ b) /\ c
を満たす場合、(A, /\)は交叉半束であるという。
交叉半束については、SparseTableというデータ構造をつかって、構築O(n * log(n)), 区間クエリO(1)で計算ができる。(更新は無理)
参考
割と内容が被っている+丁寧な記事。みなさん読むべし。
tomcatowl.github.io
tomcatowl.github.io
(2016/12/16 16:50追記)
翌日は古寺いろは@競プロ応援アカウントさんのAtCoderに毎回参加したくなる仕組みと、@ainu7さんの記事です。
