| 动态规划 (DP) |
线性 DP |
LIS、LCS、最长递增子串、编辑距离、背包一维滚动、最长公共子序列等 |
|
状压 DP |
高维前缀和、动态高维前缀和、TSP、Hamilton Path、骑士/皇后巡游 |
|
区间 DP |
石子合并、括号匹配、矩阵连乘、最优二叉搜索树 |
|
树形 DP |
普通型、换根型、树上背包、树上分组、树上直径 |
|
概率 DP |
赌徒输赢、期望步数、Markov 链 DP |
|
数位 DP |
计数型、限制型（前导零 / 不含某数字） |
|
背包 |
01 背包、无限背包、多重背包、树形背包、分组背包、混合背包、多维背包、巨大背包 |
|
记忆化搜索 |
递归+哈希 / 备忘录、不可重入状态 |
|
轮廓线 DP |
格子覆盖、最小路径覆盖、棋盘填充 |
|
插头 DP |
计数型棋盘、连通块计数 |
|
计数 DP |
有限自动机计数、组合计数 DP |
|
图上 DP |
DAG DP、最短路 DP |
|
基环树 DP |
树 + 一条环上断边枚举 |
|
自动机 DP（状态机模型） |
AC 自动机 DP、DFA DP |
|
分治 DP |
CDQ 分治 DP、整除分块 DP |
|
填坑 DP |
“填坑”序列 、平衡序列 |
|
在线 DP / 带修改 DP |
动态规划+可撤销并查集、线段树 DP |
|
DP 套 DP |
DP of DP、二重 DP（如 LCS on tree） |
|
优化 |
单调栈优化、单调队列优化、四边形不等式、斜率优化（Convex Hull Trick）、数据结构优化、决策单调性 |
| 数据结构 |
队列 |
普通队列、双端队列、单调队列 |
|
栈 |
普通栈、单调栈 |
|
链表 |
普通链表、双向链表、循环链表、跳表 / 块状链表、邻接表 & 邻接矩阵 |
|
堆 |
普通堆、对顶堆 (small-big heap)、斐波那契堆、左偏堆 |
|
线段树 |
基础线段树、权值线段树、主席树（可持久化）、李超线段树、线段树合并、zkw 线段树（非递归） |
|
树状数组 |
1D / 2D BIT、差分树状数组 |
|
平衡树 |
Splay、Treap、FHQ Treap、可持久化平衡树、AVL、替罪羊树、红黑树 |
|
并查集 |
普通并查集、带权并查集、可持久化并查集 |
|
ST 表 |
RMQ、倍增 LCA 基础 |
|
DLX |
Dancing Links |
|
KD 树 |
普通 KD、动态 KD（重构 / BBST KD） |
|
树套树 |
线段树套线段树、线段树套平衡树 |
|
笛卡尔树 |
Cartesian Tree（RMQ 递归构造） |
|
LCT |
Splay LCT、可持久化 LCT（Euler Tour Tree） |
|
虚树 |
在重链剖分 / dfs 序上快速建虚树 |
|
树链剖分 |
重链剖分、长剖（长链剖分） |
|
树的启发式合并 |
DSU on tree、启发式合并字典树 |
|
DSU on tree |
子树颜色统计、重儿子启发式 |
|
划分树 |
位次第 k 统计 |
|
析合树 |
分治图连通性 |
|
动态树 |
Euler Tour Tree、Top Tree |
|
RMQ |
ST 表、线段树、Tarjan LCA |
|
差分数组 / 前缀和 |
静态 O(1) 区间和 |
|
AC 自动机 |
fail 树、fail 树差分 |
|
SA 数组 |
DC3、SA-IS、倍增 |
|
SA 自动机 |
SAM |
|
Trie |
普通 Trie、可持久化 Trie |
|
后缀树 |
Ukkonen、McCreight |
|
回文自动机 |
PAM |
|
分块 |
经典莫队、链上分块、树上分块、带修莫队 |
|
左偏树 |
可并堆、Kruskal 重构树子堆 |
|
点分治 / 点分树 |
处理路径统计类 |
|
CDQ 分治 |
三维偏序、逆序对 |
|
仙人掌 |
无向 / 有向 |
|
pb_ds 库 |
hash table、order-statistics tree |
|
STL |
vector、priority_queue、deque … |
|
树的哈希 |
多模哈希 / 质数取模 |
|
串的哈希 |
翻转哈希、双哈希 |
|
B 树 & B+ 树 |
数据库索引 |
|
珂朵莉树 (ODT) |
区间赋值＋统计 |
|
van Emde Boas 树 |
2^w 级别字典树 |
|
不相交集合森林 |
Link-Cut like 多根 Forest 维护并查集 |
|
二叉堆 |
d-ary Heap 泛化 |
|
矩阵树 |
Kirchhoff 定理矩阵树数 |
|
回文树 |
与 PAM 重复，可合并引用 |
|
Kruskal 重构树 |
离线最小生成树集 |
|
杨表 |
Young Tableau |
|
Top Tree |
动态树另一实现 |
| 计算几何 |
基本知识 |
点集、叉积、极角序、Pick 定理 |
|
线段 / 直线 |
相交判定、交点、旋转 |
|
多边形 |
凸包、多边形包含、旋转卡壳、半平面交、重心、格点数、凸包直径、凸多边形交并、多边形核、凸包与直线集交 |
|
圆 |
交点/切线、面积交并、最小圆覆盖、圆反演、圆离散化、圆与线求交、圆与凸包求交 |
|
三角剖分 |
Delaunay、Ear Clipping |
|
扫描线 |
线段相交、矩形并面积 |
|
数值计算 |
辛普森积分、自适应辛普森、牛顿迭代、高斯求积 |
|
点定位 |
点在多边形、点在圆 |
|
凸包快速操作 |
动态凸包、半平面插入 |
|
Voronoi 图 |
Fortune 算法 |
|
最近点对 |
平面 / 三维 |
|
三维计算几何 |
点/线/面/向量旋转、长方体表面最短路、点积/叉积/混合积、四面体体积、最小球覆盖、三维凸包 |
|
三角形四心 |
重心、垂心、外心、内心 |
|
平面最小哈曼顿生成树 |
- |
|
最大空凸包 |
- |
|
平面划分 |
直线 / 圆 划分平面 |
|
费马点 |
Torricelli 点 |
|
托勒密定理 |
四边形内接圆判定 |
|
对心点 (Antipode) |
直径 & 旋转卡壳 |
|
闵可夫斯基和 |
碰撞检测 |
| 数论 |
基础与筛法 |
埃式筛、欧拉筛、线性筛、杜教筛 |
|
基本运算 |
gcd / lcm、快速幂、逆元、扩展欧几里得 |
|
定理 |
费马 / 欧拉、扩展欧拉 |
|
原根 / 阶 |
检测生成元 |
|
单位根 |
n-th root of unity |
|
类欧几里得 |
模意义下除法 |
|
同余方程组 |
CRT、扩展 CRT |
|
Lucas 定理 |
Lucas、exLucas |
|
离散对数 |
BSGS、Pohlig-Hellman |
|
整除分块 |
Dirichlet 前缀和 |
|
反演与卷积 |
狄利克雷卷积、莫比乌斯反演、单位根反演 |
|
min25 筛 |
高级质数计数 |
|
大整数质性检测 |
Miller Rabin、Pollard Rho |
|
佩尔方程 |
x² − Dy² = 1 |
|
二次剩余 |
勒让德符号、Cipolla |
|
矩阵 |
矩阵快速幂、Gauss 消元、行列式、矩阵求逆、矩阵树定理 |
|
线性递推 |
BM、常系数线性递推 |
|
组合数学 |
组合数、二项式定理、容斥原理、卡特兰数、斯特林 I&II、贝尔数、伯努利数、拆分数、错排、斐波那契、LGV 引理、Prufer 序列、杨表、Newton 恒等式 |
|
概率论 |
期望线性性、条件概率 |
|
博弈论 |
Nim、SG 函数、不平等博弈 |
|
FFT / NTT |
多项式乘法、求逆、开方、多点求值、MTT、FMT |
|
多项式 |
拉格朗日插值、多项式全家桶、FWT / FMT、生成函数 |
|
群论 |
置换群、Burnside、Polya |
|
线性规划 |
单纯形、对偶 |
|
质因数分解 |
Pollard 算法族 |
|
其他 |
单变元模线性方程、N 次剩余、平方剩余、欧拉函数、Mobius 函数、进制转换、格雷码、高精度、除数函数、积性函数、三角形数、降幂公式、Bertrand 猜想、威尔逊定理、最小二乘、哥德巴赫猜想 |
| 图论 |
图的存储 |
邻接表、前向星、链式前向星、邻接矩阵 |
|
遍历与排序 |
DFS、BFS、拓扑排序 |
|
欧拉 / 哈密顿 |
欧拉图、哈密顿图 |
|
最短路 |
Dijkstra（朴素/堆）、Bellman-Ford、SPFA、最短路径树（BFS / Dijkstra）、Floyd-Warshall、k 短路、差分约束、Floyd 最小环 |
|
最小生成树 |
Prim、Kruskal、Boruvka、次小生成树 |
|
最小树形图 |
Chu-Liu/Edmonds |
|
LCA |
Tarjan 离线、倍增、ST + DFS、树剖+线段树 |
|
直径 |
双 BFS、树 DP |
|
连接性 |
点/边双 BCC（Tarjan、割点/割边、圆方树、Kosaraju & 缩点） |
|
二分图 |
染色判定、匈牙利、Hopcroft-Karp、KM、最大匹配、DAG |
|
网络流 |
Dinic、ISAP、HLPP、Edmonds-Karp、Push-Relabel、最小费用最大流（SSP）、ZKW 费用流、Cost-Scaling、可行流、上下界流、全局最小割 |
|
2-SAT |
强连通 + 拓扑 |
|
竞赛图 |
Tournament 排序 |
|
斯坦纳树 |
Dreyfus-Wagner |
|
一般图匹配 |
Edmonds Blossom |
|
支配树 |
Lengauer-Tarjan |
|
弦图判定 |
MCS |
|
仙人掌图 |
无向 / 有向 |
|
混合图欧拉回路 |
Hierholzer |
|
限制 MST |
单边限制 MST、最优比例 MST |
|
完美消除序列 |
Chordal Graph |
|
最大团 / 极大团 |
Bron–Kerbosch、Tomita |
|
图同构 |
Weisfeiler-Lehman、AHU（树同构） |
|
Johnson |
Johnson all-pairs shortest |
|
Ford-Fulkerson |
增广路基础 |
|
推送-重贴标签 |
HLPP、前置重贴标签 |
|
树计数与编码 |
Kirchhoff、普吕弗序列、模 2 匹配数 |
| 字符串 |
基本算法 |
KMP、扩展 KMP、Manacher |
|
自动机 |
AC 自动机、SA 自动机、回文自动机、有限状态自动机 (DFA/NFA) |
|
后缀结构 |
SA 数组（DC3、SA-IS、倍增）、后缀树 |
|
哈希 |
单模 / 双模字符串哈希 |
|
最小表示 |
最大循环串、Lyndon 分解 |
|
其他 |
Rabin-Karp、Trie |
| 杂项 |
排序 |
选择、冒泡、插入、快速、归并、桶、基数、堆、希尔、计数 |
|
模拟 |
网格走迷宫、日期进位、字符串编辑 |
|
递归 / 回溯 |
N-皇后、数独、全排列 |
|
贪心 |
Huffman、排序不等式、绝对值不等式、区间调度 |
|
二分 / 三分 |
单峰函数极值、最小可行值 |
|
高精度 |
BigInteger、快速乘 |
|
前缀和 / 差分 |
一维/二维 |
|
逆序对 |
树状数组 / 归并 |
|
扫描线 |
面积并、矩形交 |
|
双指针 |
滑动窗口、尺取 |
|
倍增 |
ST、LCA、倍增跳、字符串倍增 |
|
枚举子集 / 超集 |
状压枚举、子集卷积 |
|
搜索 |
DFS、BFS、A*、IDA*、Flood Fill、DLX、折半搜索、剪枝 |
|
分治 |
树上分治、点分树、边分、动态点分、CDQ 分治 |
|
随机化 |
随机快排、爬山法、模拟退火、遗传算法、随机增量 |
|
快读 / 快写 |
getchar、ios::sync_with_stdio(false) |
|
对拍 |
随机数据 + 暴力比对 |
|
拟阵 |
最小割 = 最大流、矩阵秩 |
|
转换 / 构造 / 计算 |
基本构造题、位运算技巧 |
|
主定理 |
分治复杂度 T(n) |
|
区间树 |
Interval Tree、Segment Tree |
|
核算法 |
凸包核、核心维护 |
|
势能法 |
摇摆排序 amortized |
|
动态表 |
HashMap 负载扩容 |
|
聚合分析 |
Potentials |
|
多线程算法 |
并行归并、锁分离 |
|
NP 完全 |
SAT、TSP、VC |
|
近似算法 |
顶点覆盖、TSP、集合覆盖、LP-Round、子集和 |
|
随机化算法 |
随机数、数值随机化、舍伍德、Las Vegas、Monte Carlo |
