beet's soil

競プロのことなど

典型データ構造まとめ

なんか前回伸びたので


参考
hamayanhamayan.hatenablog.jp
ei1333's page


宣伝
beet-aizu.hatenablog.com

以下とりあえず辞書順(そのうち典型度順にしたい)

Binary Indexed Tree

一点加算、先頭からの区間和、k番目に大きい値が  O( \log N ) で可能
library/binaryindexedtree.cpp at master · beet-aizu/library · GitHub
容易に多次元に拡張が可能(実用上は2次元くらい?
library/binaryindexedtree2D.cpp at master · beet-aizu/library · GitHub


Binary Trie

二進数を管理するTrie木
全体にXOR、k番目に大きい値、lower_bound等が  O( \log N ) で可能
library/binarytrie.cpp at master · beet-aizu/library · GitHub


Dice

サイコロ 古のJAGに登場する
library/dice.cpp at master · beet-aizu/library · GitHub


Li Chao Segment Tree

傾きの単調性が要らないConvex Hull Trickができるデータ構造
library/lichao.cpp at master · beet-aizu/library · GitHub
原理はこれが詳しい
kazuma8128.hatenablog.com


Palindromic Tree

別名EERTREE 文字列に含まれる回文とその個数をO(N)で求められる
library/palindromictree.cpp at master · beet-aizu/library · GitHub
もやし先輩のスライド
mojashi.hatenablog.com


QuickFind

Disjoint Set をデータ構造をマージする一般的なテクで管理するデータ構造
sameが  O(1) 、uniteがならし  O(\log N) で行える
library/quickfind.cpp at master · beet-aizu/library · GitHub


Randomized Binary Search Tree

区間に対する操作、区間に対する取得、merge/split が  O( \log N) で可能
library/rbst.cpp at master · beet-aizu/library · GitHub
永続化すると区間のコピーもできる(できるとは言ってない)
library/prbst.cpp at master · beet-aizu/library · GitHub
yosupo.hatenablog.com


Segment Tree

区間に対する操作を管理するデータ構造
library/segtree at master · beet-aizu/library · GitHub
詳しくは以下のブログを参照
beet-aizu.hatenablog.com
beet-aizu.hatenablog.com


Skew Heap

 O( \log N) でマージ可能なヒープ 最適二分探索木とかに使う
library/skewheap.cpp at master · beet-aizu/library · GitHub


Sparse Table

束を管理するデータ構造 構築が  O(N \log N) 区間取得クエリが  O(1) で処理できる
library/sparsetable.cpp at master · beet-aizu/library · GitHub


Trie

文字列の追加・検索が空間と時間ともに  O(|S|) で行える
library/trie.cpp at master · beet-aizu/library · GitHub


UnionFind

Disjoint Set をマージテクと縮約で管理するデータ構造 unite, sameをならし  O( \alpha (x) ) で行える
library/unionfindtree.cpp at master · beet-aizu/library · GitHub
差分を管理することも可能
library/weightedunionfindtree.cpp at master · beet-aizu/library · GitHub


Wavelet Matrix

区間に含まれるvの数、区間に含まれるk番目のvの位置、区間内でk番目に大きい要素
等のクエリを  O( \log N)  O( \log A) くらいで処理できる 構築  O(N \log A)
library/waveletmatrix.cpp at master · beet-aizu/library · GitHub



伸びたらそのうち典型アルゴリズムも書くかも(自己顕示欲を満たしていくオタク)