目录
知识点目录
数据结构
基础数据结构
分块数据结构
树
可持久化数据结构
图论
最短路
生成树
回路
平面图
连通分量
网络流
杂项
字符串
匹配问题
后缀结构
回文串
杂项
动态规划
数论
基础
线性递推
定理
素性判断
同余方程
不定方程
剩余类
反演
筛法
组合数学
置换群
排列组合
容斥原理
生成树计数
杂项
多项式相关
傅里叶
多项式
生成函数
杂项
计算几何
其他数学
线性代数
博弈论
数值算法
杂项
二分
分治
莫队
二进制集合枚举
位运算
贪心
C++ 标准库
Policy Based Data Structure 库
知识点目录
数据结构
基础数据结构
☐ 数组
☐ 散列表
☐ 链表
☐ 双向链表
☐ 队列
☐ 双端队列
☐ 栈
☐ 单调队列
☐ 单调栈
分块数据结构
☐ 块状数组
☐ 块状链表
树
☐ 并查集
☐ 带权并查集
☐ 堆
☐ 树状数组
☐ 01-Trie
☐ DFS 序
☐ Prufer 序列
LCA
☐ 倍增 LCA
☐ Tarjan LCA
☐ Huffman 树
☐ 笛卡尔树
☐ 左偏树
☐ 虚树
☐ 基环树
☐ 斯坦纳树
☐ 树上启发式合并
☐ K-D Tree
线段树
☐ 基本线段树
☐ 李超线段树
☐ 区间 min-max 操作
树套树
☐ 线段树套线段树
☐ 线段树套平衡树
☐ 平衡树套线段树
点分治
☐ 静态点分治
☐ 动态点分治
☐ 边分治
平衡树
☐ Treap 随机平衡二叉树
☐ Splay 伸展树
☐ 替罪羊树
☐ AVL
☐ 红黑树
动态树
☐ LCT
树链剖分
☐ 重链剖分
☐ 长链剖分
树分块
☐ DFS 序分块
☐ 真树上分块
仙人掌
☐ 基础仙人掌
☐ 动态仙人掌
可持久化数据结构
☐ 可持久化线段树(主席树)
☐ 可持久化平衡树
☐ 可持久化 Trie
图论
最短路
☐ Dijkstra
☐ SPFA
☐ Floyd
☐ K 短路
☐ 线段树优化最短路
生成树
☐ Prim
☐ Kruskal
☐ 次小生成树
☐ 最优比率生成树
回路
☐ 欧拉回路
☐ 哈密顿回路
平面图
☐ 欧拉定理(拓扑)
☐ 平面图判定
连通分量
☐ 连通分量
☐ 强连通分量
☐ 割点
☐ 桥边
☐ 点双连通分量
☐ 边双连通分量
网络流
☐ 最大匹配 / 最小边覆盖
☐ 最大独立集 / 最小点覆盖
☐ 最大流 / 最小割
☐ König 定理
☐ 二分图最小割与最小点权覆盖
最大流
☐ Dinic(注意特殊图复杂度)
☐ 数据结构优化 Dinic
☐ Edmonds-Karp
☐ O(VE) 最大流
☐ 有上下界最大流
最小割
☐ 最小割
☐ 平面图最小割
☐ 最小点权覆盖集 / 最大点券独立集
☐ 最大权闭合子图
☐ 0/1 分数规划
☐ 全局最小割
费用流
☐ SPFA 费用流
☐ zkw 费用流
☐ 最小费用可行流
☐ 消圈定理
☐ LP 对偶费用流
二分图
☐ 匈牙利算法
☐ 最大流算法
☐ Hopcroft-Karp 算法
☐ 覆盖集和独立集
☐ DAG 的链与反链
☐ 带权二分图匹配(KM 算法)(注意复杂度)
☐ 霍尔定理
☐ 一般图最大权匹配(带花树)
杂项
☐ 拓扑排序
☐ 2-SAT(复杂度需注意)
☐ 差分约束
☐ 稳定婚姻系统
☐ 环空间
☐ 三元环计数
☐ LGV Lemma
☐ 最小点基
字符串
匹配问题
☐ KMP
☐ 扩展 KMP
☐ Trie
☐ Aho-Corasick 自动机
后缀结构
☐ 后缀数组
☐ 后缀树
☐ 后缀自动机(SAM)
☐ 广义后缀自动机
☐ SA-IS
回文串
☐ manacher
☐ PAM
☐ 回文自动机
杂项
☐ 基本 Border 理论
☐ 基本字串字典
☐ 回文串序列
☐ DFA(有限状态自动机)
☐ Huffman 编码
☐ 字符串哈希
☐ Lyndon 分解
☐ 最小表示法
动态规划
☐ 背包 DP
☐ 区间 DP
☐ DAG DP
☐ 状压 DP
☐ 数位 DP
☐ 插头 DP
☐ 可逆背包 DP
☐ 子树合并类背包 DP
☐ 单调优化 DP
☐ 分治 DP
☐ 斜率优化
☐ 四边形不等式
数论
基础
☐ GCD, LCM
☐ 欧几里得算法
☐ 更相减损术(适用于大整数)
☐ 快速幂
☐ 乘法逆元
☐ 裴蜀定理
☐ Eratosthenes 筛法
☐ Euler 筛法
线性递推
☐ Fibonacci 数列(性质)
☐ 皮萨诺周期
☐ Berlekamp-Massey 求最短递推式
☐ 拓展 BM
☐ 矩阵快速幂加速递推
定理
☐ 费马小定理
☐ 降幂大法
☐ 威尔逊定理
素性判断
☐ Miller-Rabin
☐ Pollard-Rho
同余方程
☐ BSGS
☐ exBSGS
☐ CRT
☐ exCRT
☐ Pell 方程
不定方程
☐ 拓展欧几里得算法
☐ 二元一次不定方程
☐ 类欧几里得问题
剩余类
☐ 二次剩余
☐ 三次剩余
☐ N 次剩余
☐ 任意模数 N 次剩余
反演
☐ Mobius 反演
☐ 二项式反演
☐ Stirling 反演
☐ Lagrange 反演
筛法
☐ 预处理积性函数
☐ 杜教筛
☐ 洲阁筛
☐ min_25 筛
组合数学
置换群
☐ Burnside 引理
☐ Pólya 定理
排列组合
☐ Stirling 数
☐ Catalan 数
☐ Bell 数
☐ Bernoulli 数
☐ Lucas 定理
☐ 拓展 Lucas 定理
容斥原理
☐ 递推容斥系数己算
☐ min-max 容斥
生成树计数
☐ 基尔霍夫定理(矩阵树定理)
☐ Best 定理
☐ 内向环
杂项
☐ 鸽笼原理
☐ Ramsey 定理
☐ Cantor 展开
☐ 棋盘多项式
☐ Prufer 序列相关计数
多项式相关
傅里叶
☐ FFT
☐ NTT
☐ 任意模数 NTT
☐ 子集卷积
☐ FWT
☐ 分治 FFT
多项式
☐ 多项式除法
☐ 多项式求余
☐ 多项式求逆
☐ 多项式 exp
☐ 多项式 ln
☐ 多项式开根
☐ 多项式三角函数
☐ 多项式反三角函数
生成函数
☐ 普通生成函数
☐ 指数型生成函数
☐ 二元生成函数
杂项
☐ 多项式快速多点求值
☐ 拉格朗日插值
☐ 快速插值
计算几何
☐ 半平面交
☐ 多边形
☐ 多面体
☐ 凸包的分治法
☐ 旋转卡壳
☐ 增量法
☐ 随机增量
☐ 平面解析几何及其应用
☐ 向量
☐ 点积及其应用
☐ 叉积及其应用
☐ Pick 定理
☐ 三角剖分
☐ 平面最近点对
☐ 凸多边形的交
☐ 离散化与扫描
☐ 圆反演
☐ 三维圆交
☐ 动态凸包
其他数学
线性代数
☐ 向量
☐ 矩阵
☐ 矩阵快速幂
☐ 高斯消元
☐ 行列式
☐ 线性基
☐ 线性基求并
☐ 线性基求交
☐ 矩阵微积分
博弈论
☐ SG 定理 / SG 函数
☐ 纳什均衡
☐ 威佐夫博弈
☐ Surreal Number
数值算法
☐ 自适应 Simpson 积分
☐ 爬山法
☐ 模拟退火
☐ 遗传算法
杂项
二分
☐ 整体二分
☐ 带权二分
☐ 斜率二分
分治
☐ 线段树分治
☐ CDQ 分治
莫队
☐ 普通莫队
☐ 带修莫队
二进制集合枚举
☐ 子集枚举
☐ 超集枚举
位运算
☐ bitset
☐ lowbit
☐ popcount
☐ ctz
☐ clz
贪心
☐ 拟阵
C++ 标准库
Policy Based Data Structure 库