はじめに
2020/09/14時点での僕の所持しているライブラリを(一部を除いて)解説していきます
各題目をクリックするとライブラリの該当ページに飛べるので、興味があればどうぞ(verify以上の動作保証はしません)
ライブラリ
avl
- 遅延評価のないinsert/eraseベースのAVL
- ノード管理はnewで行う
- rotate関連をtemplateでやってる事ぐらいしか書くことがない
avl_map
- std::mapと同じ役割を持つAVL
- ノード管理は配列+index
- メモリ使用量が少なく、軽い
binaryindexedtree
- BIT
- 特に言うことなし
binarylifting
- 木のダブリング
- LCAを返してくれるので、HLDを使うほどではない時に貼ったりする
bitvector
- conpactなbitvector
- access/rankのみ
- waveletmatrixの内部で使う用
compression
- 座標圧縮
- 割と使うけど面倒でverifyしていない
convexhulltrick
- CHT
- 単調性などを問わず、だいたいの操作にlogNかける実装
dinic
- 最大流
- 特に書く事がない
disjointsparsetable
- Disjoint Sparse Table
- 脳死で累積和の代わりに貼る事がある
dynamicbitvector
- 動的なビットベクトル
- 葉にboolを32個ぐらい詰め込む典型テクをしているのでメモリに優しい
- バグってる可能性あり
dynamiclazysegmenttree
- 必要な時にノードを作る遅延セグ木
- BBSTでいいので使わない
dynamicsegmenttree
- 必要な時にノードを作るセグ木
- BBSTでいいので使わない
dynamicwaveletmatrix
- 動的WaveletMatrix
- 計算量が重く、メモリも辛い
- 実装でどこかバグってるらしい
- 怖いので使いたくないし書き直したくない
eertree
- eerTree
- 回文関連がだいたいこれで殴れる
eulertour
- 前処理を線形時間で行って部分木判定をするやつ
- オイラーツアーって名前がかなり良くない
- 使った記憶がない
hashmap
- 自前ハッシュマップ
- 速いので時々使う
heavylightdecomposition
lazysegtree
- 抽象化がされている遅延セグ木
- よくある典型的な非再帰実装
lazyskiplist
lineartimesparsetable
- 線形時間構築のSparseTable
- 線形時間だと言い張るためにこういうデータ構造をよく使う事がある
lowlink
- 橋と関節点の列挙
matrix
- 行列ライブラリ
- あまり機能が多くない、行列累乗に使えるのでまぁこれでも十分
memorypool
- メモリプール
- ノード確保をstatic配列にしたりglobalに書いたりするのが嫌なので書いた
- __buitin_clzでアクセスしてるのがアホでかなり遅い
- 使う時毎回書き換えてる、いつか消したい負債
mo
- Mo's algorithm
- バグらせやすいのであると便利(後述するmo_queryと組み合わせる)
mo_query
- クエリ情報を渡すとMo's algorithmを走らせてくれる
- 全クエリ情報がまとめて手に入って便利
- インターフェースが使いやすくかなり気に入ってる
modint
- 普通のModInt
- 逆元やべき乗は別ライブラリに投げてる
persistentdynamiclazysegmenttree
- 永続動的遅延伝播セグメント木
- だいたいの場合永続遅延伝播赤黒木でなんとかなるので使わない
persistentunionfind
- 部分永続UF
- あまり使わない
primaldual
- 最小費用流
- ときどき使う事がある
redblacktree
- 普通の赤黒木
- ノード管理はmemorypool(後述する赤黒系は全てそう)
- merge/splitベース
- ランダムアクセス、区間和等 よくあるクエリは捌ける
redblacktree_lazy
- 遅延伝播赤黒木
- 普通に使う(memorypoolのせいでちょっと遅いので使う時は適宜修正する)
redblacktree_persistent
- 永続赤黒木
- コピー&ペースト、PCK20予選10等 持っていて損はない
- 人々が思ってるより実装が軽い おすすめ
redblacktree_persistent_lazy
- 永続遅延伝播赤黒木
- グラフではないを解くのに使える
redblacktree_sset
- std::setの機能の赤黒木
- ランダムアクセス付きsetとして使う
rerooting
- 全方位木DP
- 気づいたら使い方が分からなくなっていた
rollinghash
- ロリハ
- 109+7,109+9をmodにする事が多い
- まだ実戦で落ちた経験はないのでこのまま使うと思う
scc
- 強連結成分分解
- PCKとかICPC系で使う印象
scc_dag
- sccをしてからdagへの変換までやってくれる
- 返ってくる構造体が親切で使いやすいと思ってる
segmentset
- 区間をsetで管理するやつ
- 使う頻度が低いので毎回使用方法を忘れる
segmenttree
- セグ木
- よくある非再帰実装 特に言うことなし
skiplist
- スキップリスト
- 実は平衡二分木にできる操作がだいたいできる(あまり知られてない？)
- 定数倍が遅い
skiplist_sset
- スキップリストでのset実装
- あえて使う事はない
sparsetable
- 普通のSparseTable
- まぁ時々使う(LCPのテーブルとかに使う事が多い気がする)
splaytree_sset
- splay tree
- 速いしインターフェースも分かりやすいので割と使う
substrmatching
- SA-ISと文字列マッチングの詰め合わせ
- 時々使うかも
suffixtree
- SuffixTree+SA+ISA+LCPのいつものやつ
- これがあればだいたい事足りると思う
treap
- 普通のTreap
- merge/splitベース
- 最近はあまり使わない
trie
- 普通のtrie
- インターフェースがカスなので多分今後一度も使わない
- 結局直書きする事になりがち
twothreetree
- 2-3木
- 場合分けがとても多くて実装が辛かった
- 絶対使わない
twoedgeconnectedcomponents_tree
- 二重辺連結成分分解をして木にしてくれる
- 実装で困る事が多いのであると嬉しい
unionfind
- UF
- だいたいの機能が網羅されてる
- よく使う
vanemdeboastree
- vEB木 いわゆる謎木
- 実装がシンプルで実際に速い
- 空間計算量の都合で220ぐらいまでしか使えない
vanemdeboastree2
- 子をhashmapで管理するvEB木
- 実測でもsetより速い
- 値域制約がないのでかなり実用性がある
wavletmatrix
- succinctではないWaveletMatrix
- いろいろ使えるし応用もできて好き
xfasttrie
- x-fast trie
- 使わない
xfastrie_yft
- yftの土台用のx-fast trie
- y-fast trieの土台以上の価値はない
yfasttrie
- 乱数でBBSTに挿入するかを決めるy-fast trie
- vEBより遅いので使わない
yfasttrie2
- 一定サイズでBBSTのmerge/splitをするy-fast trie
- 前者よりは速い
- vEBより遅いので使わない
zdd
- ZDD
- 競プロで使わない事に気づいて整備をやめた
おわりに
整備しても一生使わないデータ構造が大変を占めていて、かなしくなった
