Wiki
競技プログラミングをするときのまとめ。まだ途中
データ構造
- セグメント木(Segment-Tree)
- BIT(Binary-Indexed-Tree)
- スパーステーブル(Sparse-Table)
- 素集合データ構造(Union-Find)
- 平衡二分探索木(RBST)
- ウェーブレット行列(Wavelet-Matrix)
- トライ木(Trie)
- スライド区間の昇順k個の和
- 長方形の和集合
- Skew-Heap
- Pairing-Heap
- Radix-Heap
- 永続配列(Persistent-Array)
グラフ
- テンプレート
- グリッド上の幅優先探索(Grid-BFS)
- 単一始点最短路(Dijkstra)
- 単一始点最短路(Bellman-Ford)
- 単一始点最短路(SPFA)
- 全点対間最短路(Warshall-Floyd)
- 最小全域木(Prim)
- 最小全域木(Kruskal)
- 最小全域有向木(Chu-Liu/Edmond)
- 最小費用流(Primal-Dual)
- 最大流(Dinic)
- 最大流(Ford-Fulkerson)
- 二部グラフの最大マッチング(Bipartite-Matching)
- 割当問題(Hungarian)
- Low-Link
- 関節点(Articulation-Points)
- 強連結成分分解(Strongly-Connected-Components)
- 二重辺連結成分分解(Biconnected-Components)
- なもりグラフ
- グラフを圧縮するやつ
木
数学
幾何
- えー
- 平面幾何の基本要素
- 点の進行方向
- 直線の直交・平行判定
- 射影・反射
- 距離
- 交差判定
- 交点
- 凸多角形判定
- 凸包
- 点-多角形包含判定
- 線分アレジメント
- ボロノイ図
- 最近点対
- 凸多角形の切断
- 多角形の面積
- 凸多角形の直径
- 3次元幾何