データ構造と代数構造

この記事は、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

サンプルコード

C++: contest/SegTree.cpp at master · koba-e964/contest · GitHub
Scala: contest/SegTree.scala at master · koba-e964/contest · GitHub
Rust: contest/SegTree.rs at master · koba-e964/contest · GitHub

BIT <=> アーベル群

(先頭からの累積和を計算するだけなら可換モノイド(= アーベル群 - 逆元 = モノイド + 可換律)でよい)
セグメント木と同じく構築O(n)、1要素の更新と区間和がO(log(n))でできる。

アーベル群の上の累積和を使う問題: 蟻本をみてください。その他自分が解いた問題の中で:
C: データ構造 - AtCoder Regular Contest 033 | AtCoder
C: 転倒距離 - AtCoder Regular Contest 043 | AtCoder
No.449 ゆきこーだーの雨と雪 (4) - yukicoder

サンプルコード

C++: contest/BIT.cpp at master · koba-e964/contest · GitHub

遅延セグメント木 <=> 作用付きモノイド

データ構造と代数(後編) · 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)で計算ができる。(更新は無理)

サンプルコード

C++: contest/SparseTable.cpp at master · koba-e964/contest · GitHub
Java: contest/SparseTable.java at master · koba-e964/contest · GitHub

ダイクストラ法 <=> closed semiring (若干おまけ)

ダイクストラ法がsemiring (R ∪ {∞}, min, +, ∞, 0) *3のsemiring構造の上で成り立っているアルゴリズムであることはよく知られている。これを一般化し、closed semiringというクラスに含まれる任意のsemiringで似たようなことができるらしい。("closed"というのは、ダイクストラ法の中で要請される色々な要請を満たす取り扱いやすい性質のことである。) 詳しくは(Mohri, 2002)を参照されたい。

(2016/12/15 12:50追記)サンプルコード

C++: contest/dijkstra.cpp at master · koba-e964/contest · GitHub
Scala: contest/Dijkstra.scala at master · koba-e964/contest · GitHub
Rust: contest/Dijkstra.rs at master · koba-e964/contest · GitHub

参考

割と内容が被っている+丁寧な記事。みなさん読むべし。
tomcatowl.github.io
tomcatowl.github.io

(2016/12/16 16:50追記)
翌日は古寺いろは@競プロ応援アカウントさんのAtCoderに毎回参加したくなる仕組みと、@ainu7さんの記事です。

*1:2016/12/15 1:39修正:e -> x,単純な誤り

*2:本来は可換でない演算に「和」という表現を使うのは望ましくないのですが、以下で紹介するBITにおける語法と整合させるため「区間和」と呼んでいます

*3:このsemiringにはTropical Semiringという名前が付いている。