分治
在当我们遇到一个数据范围很大的问题时，如果观察得到我们可以把它分解成几个更小的子问题，并且可以在线性时间中将两个子问题的答案合并，那么就可以考虑分治。
简单分治的例题有排序、平面最近点对(!!!)等。
树分治
树分治包含点分治、边分治、链分治，是用来解决一类关于树上路径的问题的算法。
点分治
首先选择一个点，将无根树变成有根树，再递归处理每一颗以根节点的儿子为根的树，然后统计。
为了使得递归层数尽量少，我们要选取原树的一个点，使得删除这个点后，剩下的联通块中最大的最小，我们称其为重心。每次处理子树时均选择重心作为分治起点，递归层数可以控制在\(\log n\)。
重心可以通过直接按照定义搜索求得。随便选一个根作为搜索起点，求出每个点的子树大小，每个点\(u\)的权值即为\(\max\{size_{v_{uk}},\cdots,n-size_u\}\)，直接找到权值最小的点即可。
例题：IOI2011 Race
给定一颗\(n\)个点的有边权的树，求一条路径使得权值和为\(K\)并且边的数量最小。\(1\leq n\leq 10^5, K\leq 10^6\)
我们考虑某条路径在点分树中的表达方式，有两种：
- 某一个点到子树根的路径。
- 来自两个子树经过子树根的拼起来的路径。
总结来说就是一条以根为\(\text{LCA}\)的路径。我们设……
边分治
在树中选择一条边，递归砍断这条边后形成的两个子树，统计与这条边有关的信息。
与点分治相似，我们也要选择一条边使得两个子树尽可能小。可是，为了保持时间复杂度在\(\log n\)级别，每个点的度数要控制在3（菊花图直接卡成\(O(n)\)）。这样可以通过加虚点和虚边来做到……
例题：BZOJ2870
给定一颗n个点的带边权的树，求树上的一条链使得链长和链最小值乘积最大。\(1\leq n\leq 100000\)
这里出现了两个不太相关的量，所以我们考虑固定一个值而求另外一个。考虑固定链最小值而求最小链长。
在处理一条边的两个子树时，对于一个子树的一个答案，另一个子树中有一个比最小值大于等于的后缀答案，用树状数组维护。
链分治
链分治把树分成许多重链，用线段树或平衡树来维护每一个重链的性质。树链剖分算是一种链分治。有许多名词：
- 重儿子
- 轻儿子
- 重边
- 轻边
- 重链
- 轻链
每次经过一条轻边到达新的一条重链时子树大小都至少会减半，进而从根节点到叶子节点最多会经过\(\log n\)条轻边，\(\log n\)条重链，每次查询的复杂度会比下面的线性数据结构多一个\(\log\)。
CDQ分治和整体二分
CDQ分治和整体二分都是离线算法。
CDQ分治
一般流程是：对于区间\([L,R]\)，递归计算\([L,M]\)和\([M+1,R]\)的贡献，然后计算\([L,M]\)对\([M+1,R]\)的贡献，相加即为答案。
例题：二维偏序
对于一个按照第一维\(a\)排序的序列，把它分成两段递归返回后，
整体二分
整体二分顾名思义，是对所有询问一起二分。他解决的问题主要是询问一些条件在第几次修改之后能够满足。
例题：Meteors
二分答案，假设当前二分的区间是\([L,R]\)，答案在区间中，线段树模拟修改，直接枚举验证查询。从左往右二分验证，每次修改只会进行一次。
三分
三分用来解决凸函数上最值的问题。例如：给定一个下凸函数\(f(x)\)（给定图像上两点连线，两点横坐标间的点都在连线下方），如何求\([L,R]\)上的最小值？
对于当前区间\([L,R]\)取三等分点\(M_1\)和\(M_2\)，如果\(f(M_1)>f(M_2)\)，则可以证明最小值不在\([L,M_1]\)之间，对于\([M_2,R]\)同理。这样每次操作后区间长度会变成原来的\(\frac{2}{3}\)，这样在\(\log_{\frac{3}{2}}n\)的时间里就可以得到要求的近似解。
分块
将区间中连续x个元素分为一个块，对于区间操作，分为整块和边角两部分处理，时间复杂度为……
例题：区间加，区间求和……
莫队
对于无修改的题目，如果知道区间\([l,r]\)的答案可以快速算出