算法模板
这里收录算法模板、板子和题单类笔记。原「算法模板」「补充算法笔记 1」「补充算法笔记 2」已整合为一套统一的算法模板，并按专题拆分。
共 10 个专题、328 个模板条目。
📚 也可以直接进入 分专题模板总览 浏览。
基础 6
搜索 7
动态规划dp 12
字符串 19
- 字符串结论
- 字符串哈希
- 二维哈希
- KMP
- 失配树
- Z函数
- Manacher
- 字典树
- 01-TRIE树合并
- AC自动机
- AC自动机与拓扑优化(求出现次数)
- 后缀数组
- 后缀自动机
- 回文自动机
- 回文自动机求双倍回文
- 判断分割两个回文串
- Lyndon分解
- 最小表示法
- 字符串结论
数学 90
- 博弈论
- 巴什博弈
- Nim博弈
- Nim-k游戏
- 阶梯nim博弈
- anti-nim(反nim游戏)
- 威佐夫博弈
- 拓展威佐夫博弈
- 斐波那契博弈
- 莫比乌斯函数
- 莫比乌斯反演
- 一般使用式子
- P2522 [HAOI2011] Problem b
- 试除法判断质数 $ O(\sqrt{N}) $
- 试除法分解质因数 $ O(logN) -O(\sqrt{N}) $
- 埃氏筛筛质数 $ O (N\sqrt{N}) $
- 质数筛 $ O(N) $
- 试除法求所有约数 $ O(\sqrt{N}) $
- 约数个数和约数之和
- 欧几里得求GCD $ O(logN) $
- 求欧拉函数 $ O(\sqrt{N}) $
- 筛法求欧拉函数
- 莫比乌斯函数筛
- 区间筛思想
- Miller-Rabin素数判断
- Pollard-Rho获取质因子
- 原根
- 类欧几里得
- 拓展欧几里得
- 组合数
- 中国剩余定理
- 拓展中国剩余定理
- Burnside定理
- Polya定理
- 生成函数
- min-max容斥
- 矩阵快速幂
- FFT
- 高精度乘法
- NTT
- 任意模数NTT(MTT)
- 三模数NTT
- FWT
- FWT求三个集合异或的不同个数
- FWT子集卷积
- 子集卷积(多个数有序)
- 子集卷积exp(多个数无序)
- 多项式板子
- 拉格朗日插值
- 重心拉格朗日插值法
- 多项式乘法逆
- 多项式求导
- 多项式求积分
- 多项式除法
- 多项式开根(a0=1)
- 多项式开根a0!=1
- 多项式对数函数（多项式 ln）
- 多项式指数函数（多项式 exp）
- 多项式多点求值
- 多项式快速幂
- BSGS(Baby Step Grant Step)
- exBSGS
- 欧拉定理
- 位进制
- 快速幂
- 高精加
- 高精减
- 高精乘低精
- 高精除低精
- 分数四则运算
- 高斯消元
- 高斯消元求行列式
- Meiseel Lehmer算法(版本一)
- Meiseel Lehmer算法(版本二)
- 二次剩余
- 裴蜀定理
- 快速幂模指数
- 类欧几里得推导
- 万能欧几里得
- 拓展欧拉定理
- 莫比乌斯反演
- 杜教筛
- LUCAS定理
- 离散对数
- Stern–Brocot 树与 Farey 序列
- 组合数学
- 特征根法求递推式
- BSGS例题：随机数生成器
- 容斥原理
- 光速幂
数据结构 61
- 对顶堆维护中位数
- 并查集
- 可撤销并查集
- 可撤销并查集与分治应用
- 分块
- ST表
- 树状数组
- 线段树
- 线段树动态开点
- 线段树分治
- 李超线段树
- 线段树(历史最值+区间加+区间取min+求和+求目前最值)
- 线段树( 区间取max+维护异或和)
- 扫描线
- Treap
- FHQ-Treap按值分裂
- FHQ-Treap按排名分裂
- FHQ-Treap文艺平衡树实现区间翻转
- 可持久化平衡树
- 可持久化文艺平衡树
- splay文艺平衡树实现区间翻转
- Splay平衡树模板
- 动态树LCT
- LCT维护边双连通分量
- LCT维护子树信息
- 线段树套平衡树( $ n(log^2n+log^3n) $ )
- 可持久化线段树
- 线段树上二分
- 可持久化trie树
- P3377 【模板】左偏树/可并堆
- 莫队
- P1903 [国家集训队] 数颜色 / 维护队列(带修莫队)
- 歴史の研究(回滚莫队)
- SP10707树上计数2(树上莫队板子)
- P4887 【模板】莫队二次离线（第十四分块(前体)）
- 点分治
- 点分树
- 点分树模板
- 笛卡尔树
- 笛卡尔树分治(启发式分裂)
- 树哈希
- Sqrt Tree
- 分块
- 树上带修莫队
- 树上莫队
- 回滚莫队
- 带修莫队
- 普通莫队
- 莫队+bitset
- 查询区间两个数等于x
- 树分块
- 线段树合并
- 线段树分裂(指针版)
- 线段树维护前缀最大值(单调递增栈)
- 可删堆
- 分块套树状数组维护二维带修
- 操作序列分块
- 矩阵乘法模板类
- 区间历史版本和板子
- 区间历史版本和(矩阵板子)
- 无根树同构
图论 70
- 删边最短路
- CF1163F Indecisive Taxi Fee
- 树上问题
- LCA
- tarjan离线求LCA
- 树链剖分HLD
- 树链剖分之重链剖分
- 树链剖分之长链剖分
- 树上启发式合并
- 拓扑排序
- 最小生成树
- prim算法
- kruskal算法
- kruskal重构树
- boruvka算法求最小生成树
- 斯坦纳树
- 最短路
- dijkstra $ O(n^2) $
- 堆优化的dijk
- SPFA
- spfa判负环
- johnson算法求带负权边的全源最短路
- 传递闭包(floyd)
- 最小环
- k短路 $ O(n^3logk) $
- 差分约束
- tarjan求强连通分量
- kosaraju算法(两次dfs求强连通分量)
- tarjan求点双连通分量
- tarjan求边双连通分量
- 动态维护边双连通分量
- 2-sat
- 2sat输出方案(n^2)
- 环计数问题
- 欧拉回路
- 【模板】欧拉路径(有向图输出字典序最小)
- 染色法判断二分图
- 匈牙利算法求解二分图
- 二分图最大权匹配（MaxAssignment 基于KM）
- Hopcroft-karp 算法
- 一般图最大匹配
- 相关应用
- 最小点覆盖：每条边都有一个点被选
- 最大独立集：选出最多的点集，使得内部没有边
- 最小路径点覆盖：用最少的互不相交的路径将点覆盖
- 最小路径重复点覆盖：路径可以相交
- 最小环
- 网络流
- Edmonds-Karps算法$ O(nm^2)(能处理10^3-10^4规模的网络) $
- Dinic算法 $ O(n^2m)(能处理10^4-10^5规模的网络) $
- Dinic封装版
- 最小费用最大流
- 费用流封装版
- 最大费用最大流
- 有上下界费用流
- 有源汇上下界费用流
- 图论问题trick
- 最小直径生成树
- 同余最短路
- Stoer-Wagner算法(求无向图最小割)
- 二分图最大权匹配
- 一般图最大匹配(带花树算法)
- Prufer序列
- LGV引理(有向无环图不相交路径计数)
- 支配树
- 线段树动态维护树的直径
- k短路
- 矩阵树定理
- tarjan求差分约束
- 圆方树
计算几何 17
- 基础知识
- 凸包
- 极角排序
- 平面最近点对
- 平面最近最远点对随机法
- 旋转卡壳求凸包直径
- 旋转卡壳求最小矩形覆盖
- k远点对
- 半平面交(求凸多边形的交集)
- 最小覆盖圆
- 三维计算几何基础
- 三维凸包
- 三角形面积并
- 最小圆覆盖
- 自适应辛普森积分
- 自适应辛普森积分求圆的面积并
- 计算积分(发散收敛)
杂项 43
- 离散化
- 悬线法
- 最大子矩阵模型
- 障碍物法求解最大子矩阵
- 置换环
- pb_ds库
- 引入
- 哈希表
- 平衡树
- 操作方法
- 普通平衡树板子
- 堆
- rope(实际为可持久化平衡树，实现块状链表)
- 曼哈顿距离与切比雪夫距离
- 异或哈希
- CDQ分治
- cdq分治离线求解二维数点问题
- 普通二维数点问题
- 动态逆序对
- bitset求解高维偏序
- bitset优化传递闭包
- bitset优化01矩阵乘法
- bitset求解字符串匹配
- color-coding算法
- 线性基
- 前缀线性基
- 区间线性基(单点修改，区间查询)()
- 区间线性基(单点插入，区间查询，猫树分治法，前缀线性基)()
- 区间线性基(区间异或，区间查询)
- 区间线性基(zak随机法)
- 二进制结论
- 01trie实现平衡树功能(32倍空间换时间)
- 替罪羊树
- 珂朵莉树
- 质数约数表
- 染色问题(思维)
- KD-Tree
- 矩阵快速幂
- 求斐波那契数列
- 矩阵快速幂求解经过n条边的最短路
- 格雷码
- dilworth定理
- wqs二分