分治（英语：Divide and Conquer），字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

From OI-wiki

主定理

假设有递推关系式 T(n) = aT(\frac{n}{b}) + f(n)，其中 n 是问题规模，a 是递推子问题数量，\frac{n}{b} 是每个子问题的规模，f(n) 为递推以外做的工作（例如合并）。

那么有

• 若 f(n)= O(n^c) 且 c<\log_b a，则 T(n)=\Theta(n^{\log_b a})​
• 若 f(n) = \Theta(n^{\log_b a})​，则 T(n)=\Theta(n^{\log_b a}\log n)；
• 若 f(n) = \Omega(n^c)​​ 且 c>\log_b a​，并且存在一个常数 k<1，使得 af(\frac{n}{b})\le kf(n) 对足够大的 n​ 都成立，则 T(n)=\Theta(f(n))。

这里的三个符号简单来说，

• O(f(n))​ 指问题的复杂度不超过 f(n)​，即 O​ 规定了问题的上界

• \Omega(f(n)) 指问题的复杂度不小于 f(n)，即 \Omega 规定了问题的下界

• 而当复杂度同时满足 O(f(n))​ 和 \Omega(f(n))​ 时，我们就说问题复杂度满足 \Theta(f(n))

注意，在算法竞赛里经常要考虑的是最坏情况，也就是尽量多考虑 O​

其实主定理可以简单理解：

• 如果分治外的操作不比 n^{\log_b(a)}​ 多，那么总的复杂度为 \Theta(n^{\log_b(a)})

  更进一步地，可以理解为如果分治外的操作比分治操作增速慢，那么就是分治操作占主要复杂度

• 如果分治外的操作数量级和 n^{\log_b(a)} 相当，那么总复杂度为 \Theta(n^{\log_b(a)}\log_n)

  这是最常见的情况，如果数量级相当，那么总复杂度还要再乘上 \log_n​

• 如果分治外操作数量级不比 n^{\log_b(a)}​ 小，那么当n很大时，总复杂度会趋向于 \Theta (f(n))

  也就是说如果分治外的操作非常慢，那么算法就会被这些操作占主导，分治的作用减弱

举个例子，归并排序的递推关系式应为 T(n) = 2 T(\frac{n}{2}) + \Theta(n)

那么 a = b = 2,f(n) = \Theta(n) = \Theta(n^{\log_22})，故 T(n) = \Theta(n \log n)

除此之外还有一种直观的方式

CDQ 分治

一般用来解决多维偏序问题。主要思想就是区间分治，然后计算左边区间对右边区间产生的贡献。

逆序对其实本质上就是一个二维偏序，所以更高维的偏序问题我们都能与逆序对类比。

回想一下，逆序对可以利用归并排序解，同时也可以利用树状数组/权值线段树来解决，这说明了实际上数据结构维护的也是一个偏序关系，并且能动态维护。

例1（三维偏序）：P3810 【模板】三维偏序（陌上花开)

有 n 个元素，第 i 个元素有 a_i,b_i,c_i 三个属性，设 f(i) 表示满足 a_j \leq a_i 且 b_j \leq b_i 且 c_j \leq c_i 且 j \ne i 的 j 的数量。

对于 d \in [0, n)，求 f(i) = d 的数量。

第一维直接当成坐标，我们可以直接进行一个排序在 \Theta(n \log n) 的时间里处理掉。

第二维利用归并排序解决（虽然我去年比较傻逼写了个 sort 导致复杂度多了 \log）

第三维就必须要上数据结构了，这里选择好写的树状数组，代码如下

int t[N];
void change(int x,int v) {for (;x <= k; x += (x & (-x))) t[x]+=v;}
int query(int x) {int ans = 0;for (;x;x -= (x & (-x))){ans += t[x];}return ans;}

struct node {
    int a,b,c,cnt,ans;
    friend inline bool operator != (const node & a,const node &b) {
        if (a.a != b.a || a.b != b.b || a.c != b.c) return 1;
        return 0;
    }
}pre[N],cdq[N];

inline bool cmp1(node x,node y) {
    if (x.a == y.a) {
        if (x.b == y.b) return x.c < y.c;
        return x.b < y.b;
    }
    return x.a < y.a;
}

inline bool cmp2(node x,node y) {
    if (x.b == y.b) return x.c < y.c;
    return x.b < y.b;
}

int vie[N],rep,tot,su[N];

void CDQ(int l,int r) {
    if (l == r) return ;
    int mid = (l + r) >> 1;
    CDQ(l,mid);
    CDQ(mid+1,r);
    sort(cdq+l,cdq+1+mid,cmp2);
    sort(cdq+mid+1,cdq+1+r,cmp2);
    int i,j = l;
    for (i = mid + 1;i <= r;++i) {
        while (cdq[i].b >= cdq[j].b && j <= mid) {
            change(cdq[j].c,cdq[j].cnt);
            ++j;
        }
        cdq[i].ans += query(cdq[i].c);
    }                                       
    for (i = l;i < j;++i) {
        change(cdq[i].c,-cdq[i].cnt);
    }
}

signed main() {
    read(n,k);
    for (int i = 1;i <= n;++i) read(pre[i].a,pre[i].b,pre[i].c);
    sort(pre+1,pre+1+n,cmp1);
    for (int i = 1;i <= n;++i) {
        ++rep;
        if (pre[i] != pre[i+1]) {
            cdq[++tot].a = pre[i].a;
            cdq[tot].b = pre[i].b;
            cdq[tot].c = pre[i].c;
            cdq[tot].cnt = rep;
            rep = 0;
        }
    }
    CDQ(1,tot);
    for (int i = 1;i <= tot;++i) {
        su[cdq[i].ans + cdq[i].cnt - 1] += cdq[i].cnt;
    }
    for (int i = 0;i < n;++i) {
        printf("%d\n", su[i]);
    }
    return 0;
}

例2：P5094 【USACO04OPEN】MooFest

数轴上有 n​ 头牛，每头牛的坐标为 x_i​，听力为 v_i​，如果第 i 头和第 j 头奶牛说话，会发出 \max\{v_i,v_j\}*|x_i-x_j| 的音量

假设每两头奶牛都在互相说话，问总的音量大小

n,x_i,v_i\leq 2\times 10^4

我会 n^2​!!!

这个柿子两边都恶心人，但是我们的直觉告诉我们先把 v_i​ 排序掉，\max 就都由右边的点提供了。这样就消掉了左边的 \max。为什么不消掉绝对值？因为绝对值相对来说好处理很多。

考虑分治，假设我们已经处理完了 [l,mid]​​​ 和 [mid+1,r]​​​ 的音量大小，那么当一个 p \in [mid+1,r]​​ 计算的时候，所有已经遍历过的左半边的元素 q​ 必定有 x_q > x_p​ ，同样，所有没有遍历过的左半边元素 q'​ 必定有 x_{q'} < x_p​ 分开计0算即可。

在合并序列的过程中，每加入一个右区间的牛 i，新增的音量为 v_i\times(\sum\limits_{左区间中满足 x_j < x_i 的 j}x_i-x_j+\sum\limits_{左区间中满足 x_j \ge x_i 的 j}x_j-x_i)，容易用前缀和快速计算。(这段话直接贺了 \color{black}C\color{red}{utest\_Junior} blog里的一句话)

代码如下

struct node {
    int v,x;
    friend inline bool operator < (const node &a,const node &b) {
        return a.v == b.v ? a.x < b.x : a.v <b.v;
    }
}p[N],q[N];

int n;
ll ans;

void solve(int l,int r) {
    if (l == r) return ;
    int mid = (l + r) >> 1;
    solve(l,mid);solve(mid+1,r);
    int pos1 = l,pos2 = mid + 1;
    ll lsum = 0,rsum = 0,lcnt = 0,rcnt = mid - l + 1;
    for (int i = l;i <= mid;++i) rsum += p[i].x;
    for (int i = l;i <= r;++i) {
        if (pos2 <= r && (pos1 > mid || p[pos2].x < p[pos1].x)) {//x_j > x_i
            ans += p[pos2].v * (lcnt * p[pos2].x - lsum);//最大值的部分
            ans += p[pos2].v * (rsum - rcnt * p[pos2].x);
            q[i] = p[pos2++];
        } else {
            lsum += p[pos1].x,rsum -= p[pos1].x;
            ++lcnt,--rcnt;
            q[i] = p[pos1++];
        }
    }
    for (int i = l;i <= r;++i) p[i] = q[i];
}

例3：P1228 地毯填补问题

相传在一个古老的阿拉伯国家里，有一座宫殿。宫殿里有个四四方方的格子迷宫，国王选择驸马的方法非常特殊，也非常简单：公主就站在其中一个方格子上，只要谁能用地毯将除公主站立的地方外的所有地方盖上，美丽漂亮聪慧的公主就是他的人了。公主这一个方格不能用地毯盖住，毯子的形状有所规定，只能有四种选择（如图）：

并且每一方格只能用一层地毯，迷宫的大小为 2^k\times 2^k 的方形。

k\leq 10

最开始填一小块肯定是如图

k = 2

k = 3​​

做完了

从大到小递归

先把整个大矩形划分为 4 块，找到公主在哪块，然后递归地去填这一块

填完之后，把中间 2\times 2 剩下的 3 个块用一个图形填满，然后递归剩下的3个

由于剩下的 3 个块每块恰好有一个，因此也可以完全套用之前的做法去解决

更进一步地，你可以发现当 k=1 的时候，这个分治策略也是适用的

2\times 2的块可以划分为 4 个块，公主在的那一块已经满了，而剩下的 3 块就是其他情况中的，中间 2\times 2 剩下的 3 个块

例4：P1429 平面最近点对（加强版）

给定平面上 n 个点，找出其中的一对点的距离，使得在这 n 个点的所有点对中，该距离为所有点对中最小的

n \leq 2\times 10 ^5

考虑分治，首先将点按照 x 进行排序。

假设我们已经处理完 x 范围在 [l,mid] 和 [mid+1,r] 的点的最短距离，实际上只要处理跨过中线 x = mid 的点对距离即可。

首先，对于左边的一个点 (x,y)，假设左右两半区间内部的最近点对距离为 d

右边的点的坐标范围必须在 (mid,y-d) 到 (mid+d,y+d) 这样一个d\times 2d的长方形上

超出这个范围的点距离一定> d，否则没有意义

然后易证，在这样一个 d\times 2d 的长方形之内，至多有 6 个点

因为如果超过 6​ 个点，则无论如何分配点的位置，距离都会小于d

因此只需要枚举每一个左边的点，再枚举右边对应方形内的点，就可以把分治外操作复杂度压到 f(n)=O(n)

这样用主定理算出来总复杂度就是 O(n\log n)

代码

struct poi {
    double x,y;
}p[N],t[N];

inline bool cmp1(poi a,poi b) {return a.x == b.x ? a.y > b.y : a.x < b.x;}
inline bool cmp2(poi a,poi b) {return a.y < b.y;}

double mindis = 1e23;
int n;

void update(poi a,poi b) {
    double dis = sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) + 0.0);
    if (dis < mindis) mindis = dis;
}

void solve(int l,int r) {
    if (r - l <= 3) {
        for (int i = l;i <= r;++i) {
            for (int j = i + 1;j <= r;++j) {
                update(p[i],p[j]);
            }
        }
        sort(p+l,p+r+1,cmp2);
        return ;
    }
    int mid = (l + r) >> 1;
    int m = p[mid].x;
    solve(l,mid);solve(mid+1,r);
    merge(p+l,p+mid+1,p+mid+1,p+r+1,t,cmp2);
    copy(t,t + r - l + 1,p + l);
    int tot = 0;
    for (int i = l;i <= r;++i) {
        if (abs(p[i].x - m) < mindis) {
            for (int j = tot-1;j >= 0 && abs(p[i].y - t[j].y) < mindis;--j) {
                update(p[i],t[j]);
            } 
            t[tot++] = p[i];
        }
    }
}

signed main() {
    scanf("%d",&n);
    for (int i = 0;i < n;++i) scanf("%lf %lf",&p[i].x,&p[i].y);
    sort(p,p+n,cmp1);
    solve(0,n-1);
    printf("%.4f",mindis);
    return 0;
}

例5：NOI2007 货币兑换

设 f[i] 为这一天的最大值，那么就有转移方程：

f_i = \max_{j<i} (\frac{f_j}{a_j\times rate_j + b_j} * (rate_j\times a_i +b_i))

这个式子的含义就是对于第 j 天的全部买入，在第 i 天全部卖出。

接下来考虑对式子变形一下：

\frac{f_i}{b_i} = \max(\frac{f_j\times rate_j}{a_j\times rate_j + b_j}\times \frac{a_i}{b_i} + \frac{f_j}{b_j + rate_j\times a_j})

这个式子可以斜率优化，x = -\frac{f_j\times rate_j}{a_j\times rate_j + b_j},y = \frac{f_j}{b_j + rate_j\times a_j},k = -\frac{a_i}{b_i}。

答案就是凸包上与斜率为 k_i 相切的点，如果在线做的话需要动态凸包，需要平衡树维护。

所以就有了 CDQ ！

我们把这个东西看作两个操作：加点和求与斜率为 k 的直线相切的点。

将操作序列二分，先求出左边的操作序列的答案，再求左边操作序列得到的凸壳对右边操作序列中询问操作的影响，最后求右边操作序列的答案。

具体来说对于第 i 天的询问，我们只要考虑 1\to i-1 上的加点，那么只需要考虑 [l,mid] 和 [mid+1,r] 的点构成的凸包的解。

那么对于 [1,i-1] 的凸包，其实就是 [1,mid] 和 [mid+1,i-1] 构成的凸包的并。

这部分其实可以直接看 cdq 本人的论文

用 [1,\frac{n}{2}] 的决策来更新 [\frac{n}{2}+1,n] 的~f[i] 值：

类似用平衡树的方法，我们可以对 [1,\frac{n}{2}] 的所有决策建立一个凸线，对[\frac{n}{2}+1,n] 的所有 i 按照 -\frac{a[i]}{b[i]} 从大到小排序，凸线的斜率是单调的，-\frac{a[i]}{b[i]}也是单调的，这样我们就可以通过一遍扫描来计算出对于每一个 i 在[1,\frac{n}{2}]里面最优的决策 j.

现在面临的问题是如何对于一段区间 [l, r] 维护出它的凸线：由于 f 值是临时计算出来的，我们只需要递归的时候利用归并排序将每一段按照 f 值从小到大排序，凸线可以临时用一个栈 O(n) 计算得出．

好接下来论文就开始讲天书了，所以自己理解一手。

整个过程实际上就是利用 CDQ 分治来维护下凸壳，这就是一个叫做 CDQ 分治维护斜率优化的思路了。

整体二分

讲课用的是蓝书上的例子，这个比较好理解。

例0：带修改区间第 k 大

利用这个例子来讲解整体二分。

整体二分这个东西的思想就在于，如何在 \log 级别的时间下同时处理多个询问，虽然说是二分，但是实际上已经是分治的过程了。

一般地，我们依然选定 mid 为答案的猜想值。接下来我们对所有询问同时进行一次判定，若答案 \leq mid 那么就分到左边，否则分到右边，递归下去进行分治。当 l = r 时，我们就对当前的所有询问找到了对应的答案。

可以使用整体二分解决的题目需要满足以下性质：

1. 询问的答案具有可二分性

2. 修改对判定答案的贡献互相独立，修改之间互不影响效果

3. 修改如果对判定答案有贡献，则贡献为一确定的与判定标准无关的值

4. 贡献满足交换律，结合律，具有可加性

5. 题目允许使用离线算法

   ——许昊然《浅谈数据结构题几个非经典解法》

如果带修改呢？比如本题的单点修改，我们把它和查询统一成一类操作，然后一起整体二分即可。

注意：如果一个询问的答案是大于 k 的，则在将其划至右侧前需更新它的 k，即，如果当前数列中小于等于 mid 的数有 t 个，则将询问划分后实际是在右区间询问第 k-t 小数。

设查询时间复杂度为 O(T)，则总时间复杂度为 O(T\log ansmax)

Tips:如果使用 vector 实现的话，会更好写，但是空间会多一点，看具体情况要不要卡常吧。

例1：ZJOI2013 K大数查询

这个题和上面那个题没啥差别，理解了就好写，就是把树状数组换成线段树区间修改就可以了。

例2：Luogu1527 矩阵乘法

把点的操作都拆了，变成有 n^2 个操作，每次在 (i,j) 上加点。

考虑查询，查询 (x_1,y_1) 到 (x_2,y_2) 这个矩阵，那么就差分一下，变成查询 x1-1 之前，[y_1,y_2] 这段和 x_2 之前，[y_1,y_2] 这段相减，得出了这个询问的值。

推荐拓展阅读：

国家集训队论文 2013 浅谈数据结构题的几个非经典解法 许昊然