様々なアルゴリズムの実装例

データ構造や数論的アルゴリズムまで、様々な分野のアルゴリズムたちを C++23 で実装しています。
アルゴリズム系の研究開発において計算機実験が必要になる場面や、 プログラミングコンテストに参加する場面などを想定して、 「実装例」または「ライブラリ」として使用することを念頭に置いています。

　

|分類|内容|具体例| |---|---|---| |DATA STRUCTURE|各種データ構造|Union-Find、Sparse Table など| |DATA STRUCTURE : SEGMENT|区間クエリに強いデータ構造|セグメント木、BIT など| |GEOMETRY|計算幾何|円の交点など| |GRAPH|グラフアルゴリズム|強連結成分分解など| |GRAPH : NETWORK FLOW|ネットワークフローアルゴリズム|Ford-Fulkerson 法など| |MATH : ALGEBRA|代数的アルゴリズム|行列計算など| |MATH : COMBINATORICS|組合せ論的アルゴリズム|modint、Nim など| |MATH : NUMBER THEORY|整数論的アルゴリズム|素因数分解、最大公約数など| |OPTIMIZATION|最適化や探索のアルゴリズム|二分探索, 三分探索など| |STRING|文字列アルゴリズム|Suffix Array、KMP 法など| |TREE|木上のデータ構造とアルゴリズム|Euler ツアー、木の直径など| |OTHERS|その他|xorshift、サイコロなど|

難易度表記の目安

• (★☆☆☆)：一般教養、NoviSteps グレード基準で 2Q 以下
• (★★☆☆)：初等典型、NoviSteps グレード基準で 1Q, 1D
• (★★★☆)：中堅典型、NoviSteps グレード基準で 2D, 3D
• (★★★★)：高度典型、NoviSteps グレード基準で 4D 以上

　

<a name="ds"></a>

データ構造 (DATA STRUCTURE)

各種データ構造の実装です

Union-Find

• (★☆☆☆) Union-Find (union by size)
• (★☆☆☆) Union-Find (union by rank)
• (★★☆☆) ポテンシャル付き Union-Find
• (★★★☆) 列挙可能 Union-Find
• (★★★☆) undo 付き Union-Find
• (★★★☆) 部分永続 Union-Find
• (★★★★) 動的 Union-Find
• (★★★★) 並列 Union-Find
• (★★★★) 領域 Union-Find
• (★★★★) 完全永続 Union-Find

ヒープ

• (★☆☆☆) 二分ヒープ
• (★★★★) Skew Heap (マージ可能ヒープ)
• (★★★★) Paring Heap (マージ可能ヒープ)
• (★★★★) Radix Heap
• (★★★★) Fibonacci Heap

キュー

• (★★☆☆) 削除可能 priority queue
• (★★★☆) 両端 priority queue (削除も可能)
• (★★★★) 永続 queue

ハッシュ

• (★★☆☆) ハッシュ
• (★★☆☆) Zobrist ハッシュ
• (★★★☆) 根付き木のハッシュ

ハッシュテーブル

• (★★★☆) ハッシュテーブル (64 bit 整数用)
• (★★★☆) ハッシュ関数
• (★★★☆) ハッシュ構造体

N 以下の非負整数の順序つき集合

• (★★☆☆) N 以下の非負整数の順序つき集合 (by BIT)
• (★★★★) N 以下の非負整数の順序つき集合 (by 64 分木)
• (★★★★) N 以下の非負整数の順序つき集合 (by van Emde Boas 木)

その他

• (★★☆☆) オンライン二部グラフ判定
• (★★☆☆) ダブリング
• (★★★☆) 並列二分探索
• (★★★★) 動的 BitSet
• (★★★★) Binary Trie
• (★★★★) Dynamic Connectivity
• (★★★★) 永続配列

　

<a name="dss"></a>

区間系データ構造 (DATA STRUCTURE : SEGMENT)

セグメント木や BIT など、区間クエリに強いデータ構造の実装です

セグメント木

• (★★☆☆) セグメント木
• (★★★☆) 遅延評価セグメント木
• (★★★☆) 二次元セグメント木
• (★★★★) 動的セグメント木
• (★★★★) 動的二次元セグメント木
• (★★★★) 永続セグメント木
• (★★★★) Segment Tree Beats (俗称)

さまざまなセグメント木

• (★★☆☆) RMQ (by セグメント木)
• (★★★☆) Starry Sky 木 (俗称)
• (★★★☆) マージソート過程木 (領域木)

Binary Indexed 木

• (★★☆☆) BIT
• (★★★☆) BIT (区間加算, 区間和取得に両対応)
• (★★★☆) 二次元 BIT
• (★★★★) 二次元 BIT (領域加算, 領域和取得に両対応)
• (★★★★) 動的 BIT
• (★★★★) 動的二次元 BIT

セグメント木・Binary Indexed 木の応用

• (★★☆☆) 転倒数
• (★★★☆) 転倒距離 (多重集合として一致する 2 系列)
• (★★★☆) 長方形の和集合

Sparse Table

• (★★★☆) Sparse Table
• (★★★★) Disjoint Sparse Table
• (★★★★) 二次元 Sparse Table

ウェーブレット行列

• (★★★★) ウェーブレット行列
• (★★★★) BIT on ウェーブレット行列 (一点加算対応)
• (★★★★) セグメント木 on ウェーブレット行列
• (★★★★) 動的ウェーブレット行列

平衡二分探索木

• (★★★★) RBST
• (★★★★) Treap
• (★★★★) Splay 木
• (★★★★) AVL 木
• (★★★★) 赤黒木
• (★★★★) 永続赤黒木
• (★★★★) 遅延伝播反転可能 RBST
• (★★★★) 遅延伝播反転可能 Treap
• (★★★★) 遅延伝播反転可能 Splay 木

各種高速化アルゴリズム

• (★☆☆☆) 累積和
• (★☆☆☆) 二次元累積和
• (★★★☆) スライド最小値
• (★★★☆) Mo 法

その他

• (★★★☆) 区間の集合を set で管理する（del and add must be invertible）
• (★★★☆) 区間の集合を set で管理する（del and add can be non-invertible）
• (★★★☆) SWAG

　 <a name="ge"></a>

幾何 (GEOMETRY)

幾何ライブラリです

• (★★★☆) 全部乗せ

基本要素

• (★☆☆☆) 基本要素 (点, 線分, 円)
• (★☆☆☆) 偏角ソート

点, 線分, 三角形などの位置関係

• (★☆☆☆) 点と線分の位置関係 (ccw)
• (★☆☆☆) 点と三角形の包含関係

射影, 交差判定, 距離

• (★☆☆☆) 射影
• (★☆☆☆) 線分と線分の交差判定
• (★☆☆☆) 線分と線分との距離

直線や円の交点

• (★☆☆☆) 直線と直線の交点
• (★★☆☆) 円と直線の交点
• (★★☆☆) 円と円の交点
• (★★☆☆) 円と線分の交点

接線

• (★★☆☆) 接線
• (★★★☆) 共通接線 (2 円)

多角形

• (★☆☆☆) 多角形の面積
• (★★☆☆) 点と多角形の包含判定
• (★★☆☆) 凸性判定
• (★★☆☆) 凸包
• (★★★☆) 凸多角形の直径
• (★★★☆) 凸多角形の切断
• (★★★☆) 凸多角形と直線の交点 O(log N)
• (★★★☆) 円と円の共通部分の面積
• (★★★☆) 円と多角形との共通部分の面積
• (★★★☆) ボロノイ図 (単純ver, O(N^3))
• (★★★★) ボロノイ図 (単純ver, O(N log N))
• (★★★★) ドロネーの三角形分割 (期待値 O(N^2))

三次元幾何

• (★★★☆) [三次元幾何一式](https://github.com/drken1215/algor