典型データ構造まとめ

なんか前回伸びたので

参考
hamayanhamayan.hatenablog.jp
ei1333's page

宣伝
beet-aizu.hatenablog.com

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

Binary Indexed Tree

一点加算、先頭からの区間和、k番目に大きい値が O(logN)$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(logN)$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)$O(1)$、uniteがならし O(logN)$O(\log N)$ で行える
library/quickfind.cpp at master · beet-aizu/library · GitHub

Randomized Binary Search Tree

区間に対する操作、区間に対する取得、merge/split が O(logN)$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(logN)$O(\log N)$ でマージ可能なヒープ　最適二分探索木とかに使う
library/skewheap.cpp at master · beet-aizu/library · GitHub

Sparse Table

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

Trie

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

UnionFind

Disjoint Set をマージテクと縮約で管理するデータ構造　unite, sameをならし O(α(x))$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(logN)$O(\log N)$か O(logA)$O(\log A)$ くらいで処理できる　構築 O(NlogA)$O(N\log A)$
library/waveletmatrix.cpp at master · beet-aizu/library · GitHub

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