一、归并排序
- 步骤：1.分解问题 2.求解子问题 3.合并子问题
二、树分治
- 主要用途：处理树上路径问题
- 点分治：首先选一个点（重心），将无根树转为有根树，再递归处理每一棵以根结点的儿子为根的子树.
- 边分治：先选边，统计删边递归（同上）（例题：BZOJ2870）
- 链分治（树链剖分）
三、CDQ分治
- 与普通分治相比，增加了计算对后面区间贡献的步骤.
- 例：二维偏序问题
四、三分
- 用于解决凸函数上最值问题
- 复杂度：
（C:精度范围）
五、分块
六、莫队
- 无修莫队（需要离线）
- 带修莫队：相当于三维莫队，增加了时间线，在时间上移动.
- 在线莫队：预处理
个信息（关键点），在此基础上进行操作
七、树上莫队
- 借助dfs序（括号序列）将树上问题转化为序列上的问题（常见思路）
- 例题：SPOJ COT2
八、块状链表
- 复杂度：定位
，插入/删除