algorithm

さまざまなアルゴリズムとデータ構造の実装例

データ構造やネットワークフローなど、さまざまな分野のアルゴリズムを C++20 で実装しています。
リンクが付いていないものは、実装予定であることを意味します。
アルゴリズム系の研究開発やプログラミングコンテストへの参加といった場面で、「実装例」「ライブラリ」として使用することを想定しています。

分類	内容	具体例
DATA STRUCTURE : BASIC	基礎的なデータ構造	Union-Find など
DATA STRUCTURE : SEGMENT	区間クエリに強いデータ構造	セグメント木など
DATA STRUCTURE : ADVANCED	その他の高度なデータ構造	永続データ構造など
FLOW	フローに関するアルゴリズム	Dinic 法など
GEOMETRY	計算幾何アルゴリズム	円の交点など
GRAPH	グラフに関するアルゴリズム	強連結成分分解など
MATH : LINEAR ALGEBRA	線形代数のアルゴリズム	行列計算など
MATH : COMBINATORICS	組合せ論的アルゴリズム	modint、Nim など
MATH : NUMBER THEORY	整数論的アルゴリズム	素因数分解など
OPTIMIZATION : SEARCH	探索ベースの最適化アルゴリズム	二分探索など
OPTIMIZATION : CONVEXITY	離散凸性に関するアルゴリズム	slope trick など
POLYNOMIAL	FPS や多項式のアルゴリズム	多項式補間、FPS 合成など
STRING	文字列に関するアルゴリズム	Suffix Array など
TREE	木上のデータ構造とアルゴリズム	Euler ツアーなど
OTHERS	その他	サイコロなど

難易度表記の目安

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

NoviSteps グレード基準

基礎的なデータ構造 (DATA STRUCTURE : BASIC)

Union-Find など、基礎的なデータ構造の実装です。

Union-Find

ヒープ・キュー

ハッシュ・ハッシュテーブル

順序付き集合

(★★☆☆) 順序付き集合 (by std::set)
(★★☆☆) N 以下の非負整数の順序付き集合 (by BIT)
(★★★☆) N 以下の非負整数の順序付き集合 (by 64 分木)
(★★★☆) Binary Trie
(★★★☆) 区間の集合を set で管理するテク (del と add が互いに逆操作である必要がある場合)
(★★★☆) 区間の集合を set で管理するテク (del と add が互いに逆操作でなくてもよい場合)

その他

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

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

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

セグメント木

(★★☆☆) セグメント木
(★★★☆) 双対セグメント木
(★★★☆) 遅延評価セグメント木
(★★★☆) 二次元セグメント木
(★★★★) Segment Tree Beats (俗称)

さまざまなセグメント木

BIT (Binary Indexed Tree)

セグメント木・BIT の応用

Sparse Table

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

ウェーブレット行列

Splay 木

(★★★★) Splay 木
(★★★★) 遅延伝播反転可能 Splay 木

赤黒木

(★★★★) 赤黒木

その他平衡二分探索木

(★★★★) RBST
(★★★★) Treap
(★★★★) AVL 木
(★★★★) 遅延伝播反転可能 RBST
(★★★★) 遅延伝播反転可能 Treap

高度なデータ構造 (DATA STRUCTURE : ADVANCED)

その他の高度なデータ構造の実装です。

高度なヒープ

(★★★★) Skew Heap (マージ可能ヒープ)
(★★★★) Paring Heap (マージ可能ヒープ)
(★★★★) Radix Heap
(★★★★) Fibonacci Heap

動的データ構造

(★★★★) 動的 bitset
(★★★★) 動的 Union-Find
(★★★★) 動的セグメント木
(★★★★) 動的二次元セグメント木
(★★★★) 動的 BIT
(★★★★) 動的二次元 BIT
(★★★★) 動的ウェーブレット行列

並列データ構造

(★★★☆) 並列二分探索
(★★★★) 並列 Union-Find

永続データ構造

(★★★★) 永続配列
(★★★★) 永続 queue
(★★★★) 永続セグメント木
(★★★★) 完全永続 Union-Find
(★★★★) 永続赤黒木

その他

(★★★☆) 根付き木のハッシュ
(★★★★) 領域 Union-Find
(★★★★) Dynamic Connectivity

ㅤ

フロー (FLOW)

フロー関連のアルゴリズムです。

(★★★★) フロー全部乗せ

最大流

(★★★☆) 最大流 (Ford-Fulkerson 法)
(★★★☆) 最大流 (Dinic 法, in O(V^2E))
(★★★☆) 最大流 (Push-Relabel 法, in O(V^2√E))
(★★★☆) フローの s-t パス・サイクルへの分解
(★★★★) 最小流量制約付き最大流

最小カット

(★★★☆) 最小カットの復元 (残余グラフから)
(★★★☆) 最小カットの構造の解明 (by 残余グラフの SCC)
(★★★★) 全域最小カット (Stoer-Wanger 法, in O(V^3))
(★★★★) Gomory-Hu 木

最小費用流

(★★★☆) 最小費用流 (Primal-Dual 法, 正辺のみ)
(★★★☆) 最小費用流 (Primal-Dual 法, 負辺対応 by ポテンシャル, 負閉路 NG)
(★★★★) 最小費用循環流 (Goldberg-Tarjan 法, by cost-scaling, 負閉路 OK)
(★★★★) 費用流の s-t パス・サイクルへの分解

最小費用 b-flow

(★★★★) 最小費用 b-flow 全部乗せ
(★★★★) 最小流量制約付き最小費用 b-flow (by primal-dual, 負閉路 NG)
(★★★★) 最小流量制約付き最小費用 b-flow (by cost-scaling)
(★★★★) 最小流量制約付き最小費用 b-flow (by ネットワーク単体法)

二部マッチング

(★★★☆) 二部マッチング (Hopcroft-Karp 法, in O(E√V))
(★★★★) 密グラフの二部マッチングの高速化 (by bitset 高速化)

重み付き二部マッチング

(★★★☆) 重み付き二部マッチング (Hungarian 法, in O(N^3))
(★★★★) 重み付き二部マッチング (LAPJV 法, in O(N^3) faster)
(★★★★) アンバランス重み付き二部マッチング (in O((K^2 log N + K^3)N))

二部マッチングの応用

劣モジュラ関数のグラフ表現

(★★★☆) Project Selection Problem (俗称：燃やす埋める)
(★★★★) 3 変数以下 2 値の劣モジュラ関数の和の最小化
(★★★★) 2 変数以下 K 値の Monge 関数の和の最小化

特殊なグラフ上の最小費用流の slope trick 帰着

(★★★★) 1 端子 + パスグラフ上の最小費用流 (by slope trick)
(★★★★) K 端子 + パスグラフ上の最小費用流 (by maroon 典型)
(★★★★) 2 x N グリッドグラフ上の最小費用流 (by series-parallel -> slope trick)

最小費用流の応用

(★★★★) 最小凸費用 b-flow (by primal-dual)
(★★★★) 最小費用テンション (最小費用流問題の双対問題)

幾何 (GEOMETRY)

幾何アルゴリズムです。

(★★★☆) 幾何全部乗せ

基本要素

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

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

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

射影, 交差判定, 距離

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

直線や円の交点

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

多角形

(★☆☆☆) 多角形の面積
(★★☆☆) 点と多角形の包含判定
(★★☆☆) 凸性判定
(★★☆☆) 凸包
(★★★☆) 凸多角形の直径
(★★★☆) 凸多角形の切断
(★★★☆) 凸多角形と直線の交点 O(log N)

円

(★★☆☆) 接線
(★★★☆) 共通接線 (2 円)
(★★★☆) 3 点を通る円
(★★★☆) アポロニウスの円
(★★★☆) 円と円の共通部分の面積
(★★★☆) 円と多角形の共通部分の面積
(★★★★) 最小包含円

ボロノイ図

(★★★☆) ボロノイ図 (単純ver, in O(N^3))
(★★★★) ボロノイ図 (O(N log N))
(★★★★) ドロネーの三角形分割 (期待値 O(N^2))

三次元幾何

(★★★☆) 三次元幾何一式
(★★★☆) 四面体 (AOJ 2060)

その他

(★★☆☆) 垂直二等分線
(★★★☆) 最近点対
(★★★☆) 線分併合
(★★★☆) 線分アレンジメント
(★★★☆) 双対変換
(★★★★) kd 木

グラフ (GRAPH)

グラフアルゴリズムです

グラフ

(★☆☆☆) グラフテンプレート
(★★★☆) ランダムツリー生成
(★★★☆) ランダムグラフ生成

グラフ探索

連結成分分解

(★★☆☆) 強連結成分分解
(★★★☆) 橋, 関節点列挙 (Low-Link)
(★★★☆) 二重辺連結成分分解 (Bridge-Block 木)
(★★★☆) 二重頂点連結成分分解 (Block-Cut 木)
(★★★★) 三重辺連結成分分解 (SPQR 木)

最短路問題

(★☆☆☆) 重みなしグラフの最短路 (by BFS, in O(E))
(★☆☆☆) 重みが 0, 1 のみのグラフの最短路 (by 0-1 BFS, in O(E))
(★☆☆☆) 単一始点最短路 (Dijkstra 法, 正辺のみ, in O(V + E log V))
(★☆☆☆) 単一始点最短路 (Bellman-Ford 法, 負辺対応, in O(VE))
(★☆☆☆) 全頂点対間最短路 (Floyd-Warshall 法, in O(V^3))
(★★★☆) 全頂点対間最短路 (Johnson 法, in O(EV log V))
(★★★☆) SPFA (Shortest Path Faster Algorithm)
(★★★☆) 最短路問題の双対問題 (俗称：牛ゲー)

全域木, 路

(★★☆☆) 最小全域木 (Kruskal 法)
(★★★☆) 有向 Euler 路
(★★★☆) 無向 Euler 路
(★★★★) 最小有向全域木 (Chu-Liu/Edmonds 法)
(★★★★) 無向グラフの全域木の個数 (行列木定理)

グラフ上の指数時間アルゴリズム

(★★★☆) 最大安定集合問題 (in O(1.381^V))
(★★★☆) 最大クリーク列挙（in O(1.443^V)）
(★★★☆) 頂点彩色 (in O(2^V V))
(★★★★) 辺彩色
(★★★★) 最小シュタイナー木 (in O(V 3^t + V^2 2^t + V^3))

一般グラフのマッチング

(★★★★) 重みなし一般グラフの最大マッチング (by 行列補間, in O(V^3))
(★★★★) 重みなし一般グラフの最大マッチング (Edmonds 法, in O(V^3))
(★★★★) 重み付き一般グラフの最大マッチング (Edmonds 法, in O(V^3))

その他

(★★☆☆) オンライン二部グラフ判定 (by Union-Find)
(★★★☆) サイクル基底 (XOR 和をとるもの)
(★★★★) 補グラフの最短路
(★★★★) 二部グラフの辺彩色 (Alon 法, in O(E log E))

線形代数 (MATH : LINEAR ALGEBRA)

行列計算など、線形代数に関するアルゴリズムです

体上の行列

環上の行列

(★★★☆) 半環上の行列 (加法・乗法, 行列累乗)
(★★★★) Euclid 環上の行列 (加法・減法・乗法, 行列累乗, 行列式 (in O(N^3 log M)))
(★★★★) Fp 係数の多項式行列 (加法・減法・乗法, 行列累乗, 行列式 (in O(N^3 D)))
(★★★★) 一般の可換環上の行列 (加法・減法・乗法, 行列累乗, 行列式 (in O(N^4)))

行列式

(★★★★) 任意 mod 行列式 (by Euclid 環上の行列式計算 in O(N^3 log M)))
(★★★★) Fp 体上の行列の特性多項式 (in O(N^3))
(★★★★) Fp 体上の行列の行列式 det(M0 + M1x) (in O(N^3))

F2 体上の線形代数

(★★★☆) F2 体上の行列 (with bitset 高速化)
(★★★☆) XOR 基底 (俗称：noshi 基底)
(★★★☆) F2 ベクトル空間の交差

その他の行列アルゴリズム

(★★★★) Strassen 法
(★★★★) 余因子行列
(★★★★) 多項式行列の prefix product M(0)M(1)…M(K-1)
(★★★★) ハフニアン (完全マッチングの個数に帰着)
(★★★★) パフィアン

さまざまな行列

(★★★★) Black Box Linear Algebra (行列式計算 in O(N^2 + N T(N)))
(★★★★) 巡回行列 (行列式計算 in O(N^2))
(★★★★) 上三角 Toeplitz 行列 (行列式計算 in O(N^2))
(★★★★) K 重対角行列 (行列式計算 in O(NK^2))
(★★★★) 二項係数行列の作用
(★★★★) スターリング数行列の作用

組合せ数学 (MATH : COMBINATORICS)

数え上げやゲームなど、組合せ数学に関するアルゴリズムです。

Modint

(★☆☆☆) Modint
(★★☆☆) 実行時に法が決まる Modint
(★★★☆) モンゴメリ乗算を用いた Modint (mod は 2^62 未満の奇数)

二項係数

(★☆☆☆) 二項係数 (オーソドックス, n<=10^7, r<=10^7, p<=10^9)
(★☆☆☆) 二項係数 (愚直計算, n<=10^9, r<=10^7, p<=10^9)
(★☆☆☆) 二項係数 (漸化式計算, n<=5000, r<=5000, p<=10^9)
(★★★☆) 二項係数 (任意 mod, n<=10^7, r<=10^7, m<=10^9)

写像12相

(★★☆☆) 重複組合せ
(★★★☆) カタラン数
(★★★☆) 分割数 P(N, K) (in O(NK))
(★★★★) 分割数 P(N) (in O(N√N))
(★★★☆) 第一種スターリング数
(★★★☆) 第二種スターリング数
(★★★☆) ベル数

その他の数

(★★★☆) ベルヌーイ数
(★★★☆) モンモール数

集合冪級数 (SPS)

(★★★☆) 高速ゼータ変換・高速メビウス変換
(★★★★) 高速アダマール変換
(★★★★) AND Convolution
(★★★★) OR Convolution
(★★★★) XOR Convolution
(★★★★) Subset Convolution
(★★★★) 集合冪級数の exp
(★★★★) 集合冪級数の合成

ゲーム

(★★☆☆) Nim
(★★☆☆) Grundy 数
(★★★★) Nim Product
(★★★★) Grundy 数と多項式環の変換
(★★★★) 超現実数

その他

(★★☆☆) LIS and LDS
(★★★★) プリューファーコード
(★★★★) 半環

整数論 (MATH : NUMBER THEORY)

整数論的アルゴリズムです。

約数, 倍数

(★☆☆☆) 約数列挙
(★☆☆☆) 最大公約数 (Euclid の互除法)
(★☆☆☆) 最小公倍数

modpow, modinv

(★☆☆☆) 拡張 Euclid の互除法
(★☆☆☆) a^n, a^{-1} (mod m)

素数

原始根, 位数, 離散対数

(★★★☆) 原始根
(★★★☆) 位数 (a^x ≡ 1 (mod p) となる最小の x)
(★★★☆) 離散対数

エラトステネスの篩

(★☆☆☆) エラトステネスの篩
(★★☆☆) エラトステネスの区間篩
(★★☆☆) 高速素因数分解, 約数列挙, メビウス関数 (エラトステネスの篩風)
(★★★★) 線形篩
(★★★★) アトキンの篩

乗法的関数

(★★☆☆) Euler のトーティエント関数
(★★★★) Euler のトーティエント関数の和
(★★★★) 高速ゼータ変換：約数倍数関係
(★★★★) 添字 GCD Convolution
(★★★★) 添字 LCM Convolution
(★★★★) Multivariate Multiplication
(★★★★) 乗法的関数の列挙
(★★★★) 乗法的関数の prefix sum の列挙
(★★★★) 無平方数の個数
(★★★★) N 以下の素数の個数 (O(N^{2/3}))

方程式

(★★★☆) 中国剰余定理
(★★★☆) 中国剰余定理 (Garner 法)
(★★★★) ペル方程式
(★★★★) 平方剰余 (Tonelli–Shanks 法)
(★★★★) Kth Root (MOD) (Tonelli–Shanks 法)

多倍長整数

(★★☆☆) 128 ビット整数
(★★★☆) 多倍長整数 (ナイーブ)
(★★★★) 多倍長整数 (高速)
(★★★★) 多倍長整数の分数
(★★★★) 多倍長整数の最大公約数

有理数

(★★★☆) 有理数
(★★★☆) Stern-Brocot 木
(★★★★) Enumerate Convex
(★★★★) Enumerate Quotients

その他

(★☆☆☆) 平衡三進法展開
(★★★☆) floor sum
(★★★★) ガウス整数

探索・最適化 (OPTIMIZATION : SEARCH)

探索や最適化に関するアルゴリズムです。

さまざまな全探索法

(★★☆☆) next_combination (nCk 通りの全探索)
(★★☆☆) 下位集合の列挙 (3^N 通りの全探索)
(★★☆☆) 上位集合の列挙
(★★☆☆) 数独ソルバー

さまざまな動的計画法

(★☆☆☆) ナップサック問題
(★☆☆☆) LIS
(★☆☆☆) LCS
(★☆☆☆) 編集距離
(★★☆☆) グリッドに含まれる最大正方形
(★★★☆) ヒストグラム長方形面積最大化
(★★★★) 最適二分探索木 (Hu-Tucker 法, in O(N log N))

さまざまな最適化技法

(★☆☆☆) 二分探索
(★★★★) Alien’s Trick — min: f(x) s.t. g(x) = K (by ラグランジュ緩和)
(★★★★) 単体法 (二段階単体法)
(★★★★) min: Σ_{i}Σ_{j} fi s.t. Σ_{i}Σ_{j} x[i][j] = C
(★★★★) 分枝限定法

SAT

(★★★☆) 2-SAT
(★★★★) SAT Solver

ヒューリスティック探索

(★★★☆) α-β 探索
(★★★☆) 焼き鈍し法
(★★★☆) A*
(★★★☆) IDA*

指数時間アルゴリズム

(★★★★) Set Cover
(★★★★) k-Cover (O(2^N N))
(★★★★) k-partition (O(2^N N^3))

ㅤ

離散凸性 (OPTIMIZATION : CONVEXITY)

離散凸性に関するアルゴリズムです。

(★★★★) Monge 全部乗せ
(★★★★) マトロイド全部乗せ

区分線形凸関数の活用 1： Slope Trick

(★★★☆) Slope Trick (傾きの変化点を管理 by priority queue)
(★★★★) Dual Slope Trick (各区間の傾きを管理 by priority queue)
(★★★★) Super Slope Trick (by Splay 木)

区分線形凸関数の活用 2： Min Plus Convolution

(★★★☆) Min Plus Convolution (凸と凸)
(★★★★) Min Plus Convolution (凸と任意)
(★★★★) Min Plus Convolution (凹と任意)
(★★★★) Axiotis-Tzamos Knapsack

区分線形凸関数の活用 3： Convex Hull Trick

(★★★☆) Convex Hull Trick (直線：傾き単調, by Deque, in O(log N)) (クエリも単調なら O(1))
(★★★★) Convex Hull Trick (直線：傾き単調でなくてよい, by Li Chao Tree, in O(log X))
(★★★★) Convex Hull Trick (直線：傾き単調でなくてよい, by Line Container, in O(log N))
(★★★★) 一般関数 Convex Hull Trick (関数挿入順：単調, by Deque, in O(log N))
(★★★★) 2D Line container (max(ax + by) クエリ)

Li Chao Tree (一般関数は Pairwise Single Crossing 性を仮定)

(★★★★) Extended Li Chao Tree (線分挿入対応, 区間一次式加算対応)
(★★★★) Extended Li Chao Tree (線分挿入対応, 区間最小値取得対応)
(★★★★) General Li Chao Tree (一般関数対応)
(★★★★) Extended General Li Chao Tree (単調な一般関数対応, 区間最小値取得対応)

行最小値問題・単一始点最短路問題

(★★★☆) Monotone 行最小値問題 (Monotone Minima, in O(H + W log H))
(★★★☆) Monotone 単一始点最短路問題 (D&D Monotone Minima, in O(N (log N)^2))
(★★★☆) TM 行最小値問題 (SMAWK 法, in O(H + W))
(★★★☆) TM 単一始点最短路問題 (D&D SMAWK 法, in O(N log N))
(★★★★) 辺コストのスライドアクセスへの対応 (Monotone Minima OK, SMAWK NG)

Monge 単一始点最短路問題

(★★★★) Monge 単一始点最短路問題 (by Convex Hull Trick, in O(N log N))
(★★★★) Monge 単一始点最短路問題 (by noshi’s 簡易 LARSCH 法, in O(N log N))
(★★★★) Monge 単一始点最短路問題 (by LARSCH 法, in O(N))
(★★★★) Monge 単一始点最短路問題スライドアクセス版 (by noshi’s 簡易 LARSCH 法, in O(N log N))
(★★★★) anti-Monge 単一始点最短路問題 (by Convex Hull Trick, in O(N log N))
(★★★★) anti-Monge 単一始点最短路問題 (by D&D SMAWK 法, in O(N log N))

その他 Monge 性, L 凸性

(★☆☆☆) Monge 性の判定 (in O(NM))
(★★★☆) Monge 行列の min-plus 合成 (in O(N^2))
(★★★☆) Monge 性 & 単調性を満たす区間 DP の Knuth-Yao Speedup (in O(N^2))
(★★★☆) Monge 単一始点 d-辺最短路の d = 1, 2, …, D における列挙 (by SMAWK 法, in O(ND))
(★★★★) Monge 単一始点 d-辺最短路問題 (by Alien DP, in O(N log N) or O(N (log N)^2))

さまざまなマトロイド

(★★★☆) 二値マトロイド
(★★★☆) グラフマトロイド
(★★★☆) 分割マトロイド
(★★★☆) 横断マトロイド
(★★★☆) マトロイド上の Greedy 法

その他マトロイド, M 凸性

(★★★★) マトロイド交差
(★★★★) 重み付きマトロイド交差
(★★★★) マトロイド Union
(★★★★) 線形マトロイドパリティ
(★★★★) 最大辺数最小重みの辺素な二つの全域森
(★★★★) 基多面体

ㅤ

形式的冪級数・多項式 (POLYNOMIAL)

形式的冪級数や多項式に関するアルゴリズムです

(★★★★) 形式的冪級数・多項式　全部乗せ

FFT, NTT, Convolution

(★★★☆) FFT (高速フーリエ変換)
(★★★☆) NTT (高速剰余変換)
(★★★☆) 任意 mod Convolution (mod < 10^9)
(★★★★) mod 2^64 Convolution
(★★★★) Relaxed Convolution
(★★★★) 二次元 FFT
(★★★★) 多変数巡回 FFT

形式的冪級数 (FPS)

(★★★★) Inv of FPS
(★★★★) Exp of FPS
(★★★★) Log of FPS
(★★★★) Pow of FPS
(★★★★) Sqrt of FPS

FPS のアルゴリズム

(★★★★) Bostan-Mori 法
(★★★★) Berlekamp-Massey 法
(★★★★) Power Projection
(★★★★) FPS の合成 (Kinoshita-Li 法, in O(N (log N)^2))
(★★★★) FPS の逆関数 (Kinoshita-Li 法, in O(N (log N)^2))
(★★★★) pow 列挙
(★★★★) 部分分数分解
(★★★★) 常微分方程式
(★★★★) 三角関数

さまざまな FPS

(★★★★) オンライン FPS
(★★★★) 多変数 FPS

多項式の基底変換

(★★★☆) Polynomial Taylor Shift (in O(N log N))
(★★★☆) Lagrange 補間 (f(0), f(1), …, f(D) -> f(x))
(★★★★) 多項式補間 (in O(N(log N)^2))
(★★★★) 多項式補間 (等比数列のとき) (in O(N log N))
(★★★★) Multipoint Evaluation (in O(M(log M)^2 + N log N))
(★★★★) Multipoint Evaluation (等比数列のとき) (by chirp z-transform, in O(N log N))
(★★★★) 多項式の基底変換：Monomial 基底 → Newton 基底 (in O(N(log N)^2))

多項式のアルゴリズム

(★★★☆) 多項式マージテク (次数の総和が D の多項式の総積 in O(D (log D)^2))
(★★★☆) 多項式の累乗 f(x)^e mod g(x)
(★★★☆) 多項式の middle product (c[i] = sum_j a[i+j]b[j])
(★★★★) 多項式の評価点シフト (in O((N + M)log(N + M))
(★★★★) 多項式の除算 (by NTT, inv of FPS, in O(N log N))
(★★★★) 多項式 GCD (by half-gcd, in O(N(log N)^2))
(★★★★) 多項式の零点を求める (mod 998244353)

さまざまな値の高速計算

(★★★★) 自然数の k 乗和 (Faulhaber の公式)
(★★★★) Σ{i=0}^{n-1} r^i i^d
(★★★★) Σ{i=0}^{∞} r^i i^d
(★★★★) Σ{i=0}^{n-1} a^i f(i)
(★★★★) N! mod P (by FPS, O(√P log P))
(★★★★) Tetration
(★★★★) 二項係数の prefix sum の多点評価
(★★★★) Karatsuba 法

文字列 (String)

文字列アルゴリズムです。

構文解析

(★★☆☆) LL(1) 再帰下降パーサ

文字列検索

(★★☆☆) ローリングハッシュ
(★★★☆) 単一パターン検索 (KMP 法)
(★★★★) 複数パターン検索 (Aho-Corasick 法)
(★★★★) 二次元ローリングハッシュ
(★★★★) セグメント木上のローリングハッシュ

Suffix Array

(★★★☆) Suffix Array
(★★★☆) Suffix Tree
(★★★☆) Suffix Automation

さまざまな文字列アルゴリズム

(★★☆☆) Z 法
(★★★☆) Manacher 法
(★★★☆) Run Enumerate

さまざまな文字列データ構造

(★★★☆) Trie 木
(★★★★) Palindromic 木 (AOJ 2292)

有名問題

(★★★☆) 文字列の相異なる subsequence の個数 (by 集める DP, in O(N))
(★★★☆) 文字列の相異なる substring の個数 (by Suffix Array, in O(N))
(★★★☆) N 個の文字列の concat のうち、辞書順最小のもの

その他

(★☆☆☆) ランレングス圧縮
(★★★★) ワイルドカードパターンマッチング

木 (Tree)

木上のクエリに答えるデータ構造や、木に関する問題を解くアルゴリズムの実装です

木

(★★★☆) 木の走査 (部分木サイズ, LCA, Euler tour など)
(★★★☆) LCA (by ダブリング)
(★★★☆) 木の直径
(★★★☆) 木の中心
(★★★☆) 木の重心
(★★★★) 木の Distance Frequency Table

木の亜種 (Functional Graph など)

木 DP

(★★☆☆) 木 DP
(★★★☆) 二乗の木 DP (俗称)
(★★★☆) 全方位木 DP
(★★★☆) 全方位木 DP (辺に重みがある場合)

Euler Tour

(★★★☆) Euler Tour
(★★★☆) LCA (by Euler Tour)
(★★★☆) 部分木加算 (by Euler Tour)

HL 分解

(★★★☆) HL 分解
(★★★☆) LCA (by HL 分解)

重心分解

(★★★☆) 重心分解

Link-Cut 木

(★★★★) Link-Cut 木
(★★★★) 部分木加算 (by Link-Cut 木)
(★★★★) 遅延伝播 Link-Cut 木

toptree

(★★★★) toptree

さまざまな木

(★★★☆) Union-Find のマージ過程を表す木
(★★★☆) Cartesian Tree
(★★★☆) Auxiliary Tree
(★★★☆) Inclusion Tree

その他の問題

(★★★☆) 強平衡二分木の Distance Frequency Table
(★★★☆) DSU on Tree
(★★★☆) 動的直径
(★★★☆) 動的 rerooting
(★★★★) Level Ancester

その他 (OTHERS)

その他のアルゴリズムです

入出力

(★☆☆☆) 各種 io ストリーム (vector, set など)
(★★★★) Fast IO

典型処理

ソート

(★☆☆☆) クイックソート
(★☆☆☆) マージソート
(★☆☆☆) ヒープソート
(★☆☆☆) 計数ソート
(★☆☆☆) 挿入ソート
(★☆☆☆) 選択ソート
(★☆☆☆) バブルソート
(★☆☆☆) シェルソート
(★☆☆☆) コムソート
(★☆☆☆) ボゴソート

その他

(★★★★) ACL
(★★☆☆) XorShift, ランダムシャッフル
(★★☆☆) タイマー
(★★☆☆) サイコロ
(★★☆☆) 曜日