模板汇总

知识点还学得不够，持续补充ing~

注：某些板子由于没有纯板子，需要删掉一些后续处理才能用（例如缩点和圆方树）

---

代数

• 矩阵乘法

  • 矩阵快速幂

• 高斯消元

  • 矩阵求行列式（任意模数）

    • Matrix-Tree 定理

• NTT

• FWT

  • 子集卷积

---

数论

• BSGS

  • 拓展 BSGS

• 线性求逆元

• 线性筛素数

• 线性基查最大值

• 线性基查 rank

• 杜教筛欧拉函数/莫比乌斯函数

• Min_25 筛

---

数据结构

• ST 表

• 线段树

  • 扫描线 （面积并）

  • 扫描线 （周长并）

• 树状数组（单点加，区间查）

• 树状数组（区间加，单点查）

  • 树状数组求逆序对

• 主席树（可持久化数组）

• 主席树（区间第 k 小）

• Splay 平衡树

  • 文艺平衡树 （区间翻转）

• 三维偏序

---

字符串

• KMP

• AC 自动机

• 后缀排序（SA）

  • 后缀数组求 LCP

• 后缀自动机（调试版）

• 后缀自动机（SAM）

---

图

• 线段树优化建图

• 前缀优化建图

• 并查集

• Kruskal 最小生成树

• Dijsktra 最短路

• Tarjan 缩点（有向图）

  • Tarjan 割点（有向图）

  • 2-SAT

• Tarjan（无向图）

  • 圆方树

• 倍增 LCA

• 树上 ST 表求 LCA

• 树上差分

• 重链剖分

• 点分治（非容斥写法）

  • 点分树

附：点分治（容斥写法）（无法处理不可删除性的信息（如最值））

• 虚树（带建树）

• Dinic 网络最大流

  • 最小割树

• SPFA+EK 最小费用最大流

---

动态规划优化

• 单调队列

  • 斜率优化

• wqs 带权二分