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

データ構造や数論的アルゴリズムまで、様々な分野のアルゴリズムたちを 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 以上

データ構造 (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 ハッシュ
(★★★☆) 根付き木のハッシュ

ハッシュテーブル

(★★★☆) ハッシュマップ
(★★★☆) ハッシュ関数
(★★★☆) ハッシュ構造体

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

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

その他

(★★☆☆) ダブリング
(★★★☆) 並列二分探索
(★★★★) 動的 BitSet
(★★★★) Binary Trie
(★★★★) Dynamic Connectivity
(★★★★) 永続配列

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

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

セグメント木

(★★☆☆) セグメント木
(★★★☆) セグメント木 (遅延評価)
(★★☆☆) RMQ (セグメント木)
(★★★☆) Starry Sky 木 (俗称)
(★★★☆) マージソート過程木 (領域木)
(★★★☆) 二次元セグメント木
(★★★★) 動的セグメント木
(★★★★) 動的二次元セグメント木
(★★★★) 永続セグメント木
(★★★★) Segment Tree Beats (俗称)

Binary Indexed 木

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

Sparse Table

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

ウェーブレット行列

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

平衡二分探索木

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

各種高速化アルゴリズム

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

その他

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

幾何 (GEOMETRY)

幾何ライブラリです

(★★★☆) 全部乗せ

基本要素

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

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

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

射影, 交差判定, 距離

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

直線や円の交点

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

接線

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

多角形

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

三次元幾何

(★★★☆) 三次元幾何一式

その他

(★★☆☆) 垂直二等分線
(★★★☆) 3 点を通る円
(★★★☆) アポロニウスの円
(★★★☆) 最近点対
(★★★★) 最小包含円
(★★★☆) 線分併合
(★★★☆) 線分アレンジメント
(★★★☆) 双対変換
(★★★★) kd 木

グラフ (GRAPH)

グラフアルゴリズムです

グラフ探索

連結成分分解

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

最短路問題 (基本)

(★☆☆☆) 重みなしグラフの最短路 (BFS, in O(E))
(★☆☆☆) 重みが 0, 1 のみのグラフの最短路 (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(V 3^t + V^2 2^t + V^3))

その他

(★★★☆) ランダムグラフ生成
(★★★☆) 最大安定集合問題 (in O(1.381^V))
(★★★☆) 最大クリーク列挙（in O(1.443^V)）
(★★★☆) 頂点彩色 (in O(2^V V))
(★★★★) 辺彩色
(★★★★) 二部グラフの辺彩色 (Alon 法, in O(E log E))

ネットワークフロー (GRAPH : NETWORK FLOW)

グラフネットワークフロー関連のアルゴリズムです

最大流

(★★★☆) 最大流 (Ford-Fulkerson 法)
(★★★☆) 最大流 (Dinic 法)

最小カット

(★★★☆) 最小カット (= 最大流)
(★★★★) 全域最小カット (Stoer-Wanger 法)
(★★★★) 全頂点対間最小カット (Nagamochi-Ibaraki 法)
(★★★★) Gomory-Hu 木

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

(★★★☆) Project Selection Problem (俗称: 燃やす埋める)
(★★★☆) 2 変数劣モジュラ関数の和を表す最小カット (燃やす埋めるの一般化)
(★★★★) 3 変数劣モジュラ関数の和を表す最小カット (燃やす埋めるの一般化)

マッチング

(★★★☆) 二部マッチング (Hopcroft-Karp 法, O(E√V))
(★★★☆) 重みつき二部マッチング (Hungarian 法)
(★★★★) 一般グラフの最大マッチング (Edmonds 法)
(★★★★) 一般グラフの最大マッチング (行列補間)
(★★★★) 重み付き一般グラフの最大マッチング

マッチングの応用

(★★★☆) 二部グラフの最大独立集合
(★★★☆) 二部グラフの最小点被覆
(★★★☆) 二部グラフの最小辺被覆
(★★★☆) DAG の最小パス被覆

最小費用流

(★★★☆) 最小費用流 (Primal-Dual 法, 正辺のみ)
(★★★☆) 最小費用流 (Primal-Dual 法, 負辺対応 by ポテンシャル, 負閉路 NG)

最小費用 b-flow

(★★★★) 最小費用循環流 (Goldberg-Tarjan 法, by cost-scaling, 負閉路 OK)
(★★★★) 最小費用 b-flow (by cost-scaling)
(★★★★) 最小費用 b-flow (by ネットワーク単体法)

最小費用流の応用

(★★★★) 需要供給量にも上限と下限を設けた最小費用 b-flow の拡張
(★★★★) 最小費用テンション (最小費用流問題の双対問題)
(★★★★) 最小凸費用流
(★★★★) 最小凸費用テンション (最小凸費用流問題の双対問題)

代数 (MATH : ALGEBRA)

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

体上の行列

(★★★☆) 実数体上の行列 (加法・減法・乗法, 行列累乗, 行列式 (in O(N^3)), 逆行列 (in O(N^3)))
(★★★☆) Fp 体上の行列 (加法・減法・乗法, 行列累乗, 行列式 (in O(N^3)), 逆行列 (in O(N^3)))
(★★★☆) F2 体上の行列 (with bitset 高速化)
(★★★☆) 一般の可換体上の行列 (加法・減法・乗法, 行列累乗, 行列式 (in O(N^3)), 逆行列 (in O(N^3)))

環上の行列

(★★★☆) 半環上の行列 (加法・乗法, 行列累乗)
(★★★★) 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))

行列のアルゴリズム

(★★★☆) 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))
(★★★★) 二項係数行列の作用
(★★★★) スターリング数行列の作用

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])
(★★★★) 多項式の評価点シフト (O((N + M)log(N + M))
(★★★★) 多項式の除算 (by NTT, inv of FPS, O(N log N))
(★★★★) 多項式 GCD (by half-gcd) (O(N(log N)^2))
(★★★★) 多項式の零点を求める (mod 998244353)

さまざまな値の高速計算

(★★★☆) floor sum
(★★★★) 自然数の 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 法

組合せ (MATH : COMBINATORICS)

組合せ論的アルゴリズムたちです

二項係数

(★☆☆☆) 二項係数 (オーソドックス, 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)

さまざまな数

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

高速なソート

(★☆☆☆) クイックソート
(★☆☆☆) マージソート
(★☆☆☆) ヒープソート
(★☆☆☆) 計数ソート

さまざまなソート

(★☆☆☆) 挿入ソート
(★☆☆☆) 選択ソート
(★☆☆☆) バブルソート
(★☆☆☆) シェルソート
(★☆☆☆) コムソート
(★☆☆☆) ボゴソート

集合族に関する問題

(★★★☆) 2-SAT
(★★★☆) マトロイド上の Greedy 法
(★★★★) マトロイド交差

集合冪級数 (SPS)

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

ゲーム

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

その他

(★★☆☆) LIS and LDS
(★★☆☆) 転倒数
(★★★☆) 転倒距離 (多重集合として一致する 2 系列)
(★★★★) プリューファーコード
(★★★★) 半環

整数 (MATH : NUMBER THEORY)

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

Modint

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

約数, 倍数

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

素数

エラトステネスの篩

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

乗法的関数

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

方程式

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

多倍長整数

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

有理数

(★★★☆) 有理数
(★★★☆) Stern-Brocot 木
(★★★★) Stern-Brocot 木上の二分探索
(★★★★) Enumerate Convex
(★★★★) Enumerate Quotients

その他

最適化, 探索 (OPTIMIZATION, SEARCH)

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

さまざまな全探索

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

動的計画法

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

Convex Hull Trick

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

Monge 性を活用する DP 高速化技法

(★★★☆) Monotone 行最小値問題 (Monotone Minima, O(H + W log H))
(★★★☆) Monotone 単一始点最短路問題 (D&D Monotone Minima, O(N (log N)^2))
(★★★☆) TM 行最小値問題 (SMAWK, O(H + W))
(★★★☆) TM 単一始点最短路問題 (D&D SMAWK, O(N log N))
(★★★★) Monge 単一始点最短路問題（by noshi's 簡易 LARSCH, O(N log N))
(★★★★) Monge 単一始点最短路問題（by LARSCH, O(N))
(★★★★) Monge グラフ上の d-辺最短路
(★★★★) Monge グラフ上の d-辺最短路の d = 1, 2, ..., N における列挙
(★★★★) Aliens DP

その他の DP 高速化技法

(★★★★) Slope Trick
(★★★★) Min Plus Convolution (凸と任意)
(★★★★) Min Plus Convolution (凸と凸)
(★★★★) Min Plus Convolution (凹と任意)

数理最適化

(★☆☆☆) 二次方程式
(★☆☆☆) 二分探索法 (方程式の解を 1 つ求める)
(★★☆☆) 三分探索法
(★★☆☆) 黄金探索法
(★★★☆) Newton 法
(★★★★) 単体法 (二段階単体法)
(★★★★) 分枝限定法
(★★★★) SAT Solver

さまざまな探索法

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

指数時間アルゴリズム

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

文字列 (String)

文字列アルゴリズムです

構文解析

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

文字列検索

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

Suffix Array

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

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

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

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

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

その他

(★☆☆☆) ランレングス圧縮
(★★☆☆) 各 index 以降で各文字が最初に登場する index を求める関数
(★★★☆) 文字列の相異なる subsequence の個数 (by 配る DP (in O(cN)))
(★★★☆) 文字列の相異なる subsequence の個数 (by 集める DP (in O(N)))
(★★★☆) 文字列の相異なる substring の個数 (by Suffix Array (in O(N)))
(★★★★) ワイルドカードパターンマッチング

木 (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)

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

入出力

(★★★★) Fast IO

グリッド

(★☆☆☆) グリッドの 4 近傍, 8 近傍
(★☆☆☆) ハニカムの 6 近傍

その他

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

コードテンプレート

License

These codes are licensed under CC0.

Name		Name	Last commit message	Last commit date
Latest commit History 707 Commits
DataStructure		DataStructure
DataStructureSegment		DataStructureSegment
Geometry		Geometry
Graph		Graph
GraphNetworkFlow		GraphNetworkFlow
MathAlgebra		MathAlgebra
MathCombinatorics		MathCombinatorics
MathNumberTheory		MathNumberTheory
Optimization		Optimization
Others		Others
String		String
Tree		Tree
LICENSE		LICENSE
README.md		README.md
template_atcoder.cpp		template_atcoder.cpp
template_minimum.cpp		template_minimum.cpp

Folders and files

Latest commit

History

Repository files navigation