知识树 | 菜王的 blog

知识树

2023-04-15

数据结构
- 并查集
  - 普通并查集
  - 拓展域 / 边带权并查集
- 树状数组
- 线段树
  - 线段树合并
  - 猫树
- 分块
- 莫队
  - 普通莫队
  - 带修莫队
  - 回滚莫队
- 重链剖分
- 点分治
- 笛卡尔树
- BST 与平衡树
- CDQ 分治
- 整体二分
- 可持久化数据结构
  - 可持久化 Trie
  - 可持久化线段树
  - 可持久化并查集
DP
- 线性 DP
- 背包 DP
- 区间 DP
- 树形 DP
- 状压 DP
- 计数 DP
- 数位 DP
- 环形 DP
- 高斯消元求解带后效性 DP
- 单调队列优化 DP
- 倍增优化 DP
- 数据结构优化 DP
- 斜率优化 DP
- 四边形不等式优化 DP
- 概率 DP
图论
- DFS
- LCA
- 最短路
  - BFS
  - 01-BFS
  - Dijkstra
  - Floyd
  - SPFA
- 拓扑排序
- 最小生成树
- Tarjan 缩点
  - 割点
  - 桥
- 网络流
数论
- 欧几里得算法
  - 拓展欧几里得算法
- 中国剩余定理（CRT）
- 拓展中国剩余定理（exCRT）
- 乘法逆元
- 数论函数 & Dirichlet 卷积
- 线性基
字符串
- 字符串哈希
- 最小表示法
- KMP
- Trie
- AC 自动机
- 后缀数组
计数

下一篇：valuable 的思维题