学习笔记：cdq 分治

CGcgxyXY · 2026-08-10 00:37:05 · 算法·理论

介绍

cdq 分治是陈丹琦总结出的算法，也因此得名。
2008 国集论文。

cdq 分治主要用于解决带有偏序条件的问题，例如操作序列的时间偏序，一维 dp 的下标偏序，或者多维偏序统计等等。

cdq 分治的流程如下：
首先保证序列按任意一个偏序维排序，这里记为 a_i。
那么序列满足 a_i 单调。
特别地，如果偏序条件包含 a_i 相等，那么需要按照其他维的偏序排序。
如果出现所有维都相等的情况，可以合并这些元素或者再添加一维。

记当前处理的区间为 [l,r]。
如果 l=r ，计算单点贡献之后直接返回。
否则以区间中点 mid=\lfloor \frac{l+r}{2} \rfloor 为分界点，把 [l,r] 划分为左区间 [l,mid] 和右区间 [mid+1,r]。
对于跨区间的贡献单独计算，不跨区间的贡献递归计算。

由于排序，第 j 个元素对第 i 个元素有贡献当且仅当 j<i（j=i 特殊处理，作为单点贡献）。
左区间下标范围是 [l,mid]，右区间下标范围是 [mid+1,r]。
由于 mid<mid+1，显然 \forall j \in [l,mid],i \in [mid+1,r]，j 对 i 都有贡献。
因此 cdq 分治过程的更新显然是正确的。

将分治树画出来：（借用一下 OI Wiki 的图）

可以发现，\forall j \le i，j 对 i 的贡献在 [j,j] 与 [i,i] 在树上节点对应的 LCA 节点所代表的区间 [l,r] 计算。
因此，cdq 分治可以不重不漏的计算所有 (j,i) 对的贡献。

一般地，递归与计算的先后顺序不会影响答案。
特别地，对于 DP 等类需要用更新后的 j 更新 i 的问题，需要在递归树上中序遍历以保证更新时 j 的值是正确的。

cdq 分治的作用可以看作消掉了一维偏序条件，可以看作将修改查询混杂变成先若干修改后若干查询，也可以看作在线转离线。

cdq 分治的时间复杂度是递归计算的，一般需要用到主定理。

cdq 分治优势有许多：常数小，空间占用小，好写等等，可以通过例题自行体会。

此外，cdq 分治还可以处理和区间最值 / 区间最值位置相关的信息，可见这一篇文章。

例题

统计类

P3810 【模板】三维偏序 / 陌上花开

Description：

有 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 的数量。

Solution:

对每一个 i，计算 \sum_{j \in [1,n]}[a_j \le a_i][b_j \le b_i][c_j \le c_i] 的值，然后使用桶统计即可。

考虑使用 cdq 分治。

由于可能出现完全相同的元素，需要特别处理。

:::info[Sol 1] 将相同的元素合并成一个，处理带权的值。

由于 a_i 仍然有可能相同，需要以三维分别为三个关键字进行排序，以确保所有有贡献的 j 都能被统计到。

最后需要去掉 i 对自身的贡献。

显然变成一个二维偏序（或者说二维数点）。

解法很多，这里选择排序后使用权值树状数组维护。

时间复杂度 T(n)=2T(\frac{n}{2})+O(n \log V)，主定理得到是 O(n \log n \log V)。

空间复杂度 O(n+k+V)。

可以发现，处理偏序条件的方法有许多，例如排序、数据结构、cdq 分治。
每一种方法都可以处理掉一维偏序，同样可以推广到更高维。
具体可以见四维偏序的例题。

另外介绍两种优化：
归并优化：对于需要将区间元素排序，并且排序的关键值不变的题目，可以使用归并排序以减小常数。
暴力优化：分析复杂度，当区间大小不超过一定值（通常需要复杂度分析确定）时可以采用暴力。

Code

:::info[Sol 1]

#include<bits/stdc++.h>
using namespace std;
#define rep(a,b,c) for(int a=(b);a<=(c);a++)
const int N = 1e5 + 5, V = 2e5 + 5;
int n, k;
struct elem {
    int a, b, c, w, ans;
    bool operator == (const elem & x) const{return a == x.a && b == x.b && c == x.c;}
    bool operator < (const elem & x) const{return a == x.a ? b == x.b ? c < x.c : b < x.b : a < x.a;}
} a[N],b[N];
bool cmp(const elem & x, const elem & y){return x.b == y.b ? x.c < y.c : x.b < y.b;}
int tot;
int t[V];
void add(int p, int x){
    while (p <= k) t[p] += x, p += p &-p;
}
int sum(int p){
    int res = 0;
    while (p) res += t[p], p &= p - 1;
    return res;
}
void cdq(int l, int r){
    if (l >= r) return;
    int mid = (l + r) >> 1;
    if (r - l <= 15){
        rep(i, l, r) rep(j, l, i - 1) if (a[j].b <= a[i].b && a[j].c <= a[i].c) a[i].ans += a[j].w;
        sort(a + l, a + r + 1, cmp);
        return;
    }
    cdq(l, mid);
    cdq(mid + 1, r);
    int j = l;
    rep(i, mid + 1, r){
        while (j <= mid && a[j].b <= a[i].b) add(a[j].c, a[j].w), ++j;
        a[i].ans += sum(a[i].c);
    }
    rep(i, l, j - 1) add(a[i].c,-a[i].w);
    int p = j = l;
    rep(i, mid + 1, r){
        while (j <= mid && a[j].b <= a[i].b) b[p++] = a[j++];
        b[p++] = a[i];
    }
    while (j <= mid) b[p++] = a[j++];
    rep(i, l, r) a[i] = b[i];
}
int cnt[N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> k;
    rep(i, 1, n){
        int x, y, z;
        cin >> x >> y >> z;
        a[i] = {x, y, z, 1, 0};
    }
    sort(a + 1, a + n + 1);
    rep(i, 1, n){
        if (tot && a[i] == a[i - 1])++b[tot].w;
        else b[++tot] = a[i];
    }
    rep(i, 1, tot) a[i] = b[i];
    cdq(1, tot);
    rep(i, 1, tot) cnt[a[i].ans + a[i].w - 1] += a[i].w;
    rep(i, 0, n - 1) cout << cnt[i] <<  '\n';
    return 0;
}

::: :::info[Sol 2]

#include<bits/stdc++.h>
using namespace std;
#define rep(a,b,c) for(int a=(b);a<=(c);a++)
const int N = 2e5 + 5, V = 2e5 + 5;
int n, k;
struct elem {
    int a, b, c, id;
    bool operator < (const elem & x) const{return a == x.a ? id < x.id : a < x.a;}
} a[N],b[N];
int ans[N];
int t[V];
void add(int p, int x){
    while (p <= k) t[p] += x, p += p &-p;
}
int sum(int p){
    int res = 0;
    while (p) res += t[p], p &= p - 1;
    return res;
}
void cdq(int l, int r){
    if (l >= r) return;
    int mid = (l + r) >> 1;
    cdq(l, mid);
    cdq(mid + 1, r);
    int j = l;
    rep(i, mid + 1, r){
        while (j <= mid && a[j].b <= a[i].b){
            if (!a[j].id) add(a[j].c, 1);
            ++j;
        }
        if (a[i].id) ans[a[i].id] += sum(a[i].c);
    }
    rep(i, l, j - 1) if (!a[i].id) add(a[i].c,-1);
    int p = j = l;
    rep(i, mid + 1, r){
        while (j <= mid && a[j].b <= a[i].b) b[p++] = a[j++];
        b[p++] = a[i];
    }
    while (j <= mid) b[p++] = a[j++];
    rep(i, l, r) a[i] = b[i];
}
int cnt[N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> k;
    rep(i, 1, n){
        int x, y, z;
        cin >> x >> y >> z;
        a[i] = {x, y, z, 0};
        a[n + i] = {x, y, z, i};
    } sort(a+1,a+n*2+1);
    cdq(1, n * 2);
    rep(i, 1, n)++cnt[ans[i] - 1];
    rep(i, 0, n - 1) cout << cnt[i] << '\n';
    return 0;
}

:::

P4390 [BalkanOI 2007] Mokia 摩基亚

Description

维护一个平面，每个点有权值，初始均为 0。
要求支持两种操作：
类型 1：点 (x,y) 的权值添加 w。
类型 2：查询矩形 (x1,y1,x2,y2) 内所有点的总权值。

Solution

从偏序的角度来看：

一个操作 1 的 (x,y,w) 对一个操作 2 的 (x1,y1,x2,y2) 有 w 的贡献当且仅当 x \in [x1,x2] \land y \in [y1,y2] \land t<t'。
其中 t 为操作 1 的时间，t' 为操作二的时间。