概述
CDQ分治是一种 powerful 的离线算法技巧，由陈丹琦在2008年信息学竞赛中系统总结并推广。其核心思想是：通过分治将多维问题降维，将在线问题转化为离线问题，从而使用更低维度的数据结构高效求解。本文将用Java实现CDQ分治解决经典的三维偏序问题，帮助读者掌握这一高级算法设计范式。
问题定义
三维偏序问题
给定N个三元组 (a, b, c)，对于每个三元组i，求满足 a_j ≤ a_i 且 b_j ≤ b_i 且 c_j ≤ c_i 的j的个数（包含i自身）。
暴力解法需要 O(N²) 时间。使用CDQ分治 + 树状数组可将复杂度降至 O(N log² N)。
核心思想
CDQ分治的本质是降维：
- 第一维：按a排序，保证左半部分的a始终 ≤ 右半部分的a
- 第二维：在分治过程中，递归处理左右两半，然后合并时按b归并排序
- 第三维：合并过程中，用树状数组维护c维度，实现O(log N)查询
这样就将三维问题成功降为使用一维数据结构（树状数组）处理。
Java实现
数据结构与树状数组
import java.util.*;
public class CDQDivideAndConquer {
/**
* 三维点结构
*/
static class Point {
int a, b, c; // 三维坐标
int id; // 原始编号
int count; // 当前点贡献的答案（去重后的计数）
int ans; // 最终答案（包含重复点）
Point(int a, int b, int c, int id) {
this.a = a; this.b = b; this.c = c;
this.id = id;
this.count = 0;
this.ans = 0;
}
}
/**
* 树状数组（Fenwick Tree）：维护c维度的前缀和
*/
static class FenwickTree {
private final int[] tree;
private final int size;
public FenwickTree(int size) {
this.size = size;
this.tree = new int[size + 2];
}
/**
* 在位置pos增加val
*/
public void add(int pos, int val) {
while (pos <= size) {
tree[pos] += val;
pos += pos & -pos; // lowbit
}
}
/**
* 查询[1, pos]的前缀和
*/
public int query(int pos) {
int sum = 0;
while (pos > 0) {
sum += tree[pos];
pos -= pos & -pos;
}
return sum;
}
/**
* 清空（用于分治的各轮之间）
*/
public void clear(int pos) {
while (pos <= size) {
if (tree[pos] == 0) break;
tree[pos] = 0;
pos += pos & -pos;
}
}
}
private Point[] points;
private Point[] temp; // 归并排序临时数组
private FenwickTree bit;
private int[] finalAnswer;
CDQ分治核心
/**
* CDQ分治主函数
* @param l 左边界（包含）
* @param r 右边界（包含）
*
* 处理流程：
* 1. 按b归并排序，保证左右两半内部按b有序
* 2. 递归处理左半部分 [l, mid]
* 3. 递归处理右半部分 [mid+1, r]
* 4. 统计左半部分对右半部分的贡献（核心步骤）
* 5. 按b归并合并左右两半
*/
public void cdq(int l, int r) {
if (l >= r) return;
int mid = (l + r) >> 1;
cdq(l, mid);
cdq(mid + 1, r);
// 核心步骤：统计左半部分对右半部分的贡献
// 由于递归后左右两半各自按b有序，使用双指针 + 树状数组统计
int i = l, j = mid + 1;
while (j <= r) {
// 将左半部分所有b <= 右半部分当前b的点加入树状数组
while (i <= mid && points[i].b <= points[j].b) {
bit.add(points[i].c, points[i].count);
i++;
}
// 查询树状数组中c <= 当前右半部分点的c的点的数量
points[j].ans += bit.query(points[j].c);
j++;
}
// 清理树状数组（只清理加入过的位置）
for (int k = l; k < i; k++) {
bit.clear(points[k].c);
}
// 按b归并排序，保证整体有序
mergeByB(l, mid, r);
}
/**
* 按b值归并合并 [l, mid] 和 [mid+1, r]
*/
private void mergeByB(int l, int mid, int r) {
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r) {
if (points[i].b <= points[j].b) {
temp[k++] = points[i++];
} else {
temp[k++] = points[j++];
}
}
while (i <= mid) temp[k++] = points[i++];
while (j <= r) temp[k++] = points[j++];
System.arraycopy(temp, 0, points, l, k);
}
完整求解流程
/**
* 求解三维偏序问题
* @param rawPoints 原始三维点数组
* @return 每个点对应的答案数组
*/
public int[] solve(Point[] rawPoints) {
int n = rawPoints.length;
// 第一步：按a排序（处理第一维）
Arrays.sort(rawPoints, (p1, p2) -> {
if (p1.a != p2.a) return p1.a - p2.a;
if (p1.b != p2.b) return p1.b - p2.b;
return p1.c - p2.c;
});
// 第二步：去重，统计相同点的数量
// 完全相同的点只保留一个，count记录重复次数
List<Point> uniqueList = new ArrayList<>();
for (int i = 0; i < n; ) {
int j = i;
while (j < n && rawPoints[j].a == rawPoints[i].a
&& rawPoints[j].b == rawPoints[i].b
&& rawPoints[j].c == rawPoints[i].c) {
j++;
}
Point p = rawPoints[i];
p.count = j - i; // 相同点的数量
p.ans = p.count; // 至少包含自身
uniqueList.add(p);
i = j;
}
int m = uniqueList.size();
points = uniqueList.toArray(new Point[0]);
temp = new Point[m];
// 第三步：对c坐标离散化（压缩到1~m范围）
int[] allC = new int[m];
for (int i = 0; i < m; i++) allC[i] = points[i].c;
Arrays.sort(allC);
Map<Integer, Integer> cMap = new HashMap<>();
int rank = 1;
for (int c : allC) {
if (!cMap.containsKey(c)) {
cMap.put(c, rank++);
}
}
for (Point p : points) {
p.c = cMap.get(p.c);
}
// 初始化树状数组
bit = new FenwickTree(rank);
// 第四步：CDQ分治（处理第二维和第三维）
cdq(0, m - 1);
// 第五步：将答案映射回原始点
finalAnswer = new int[n];
for (Point p : points) {
// ans已经包含了所有满足偏序关系的点的count之和
finalAnswer[p.id] = p.ans;
}
return finalAnswer;
}
测试与验证
public static void main(String[] args) {
CDQDivideAndConquer solver = new CDQDivideAndConquer();
// 构造测试数据
Point[] points = new Point[]{
new Point(1, 2, 3, 0),
new Point(2, 2, 3, 1),
new Point(2, 3, 4, 2),
new Point(1, 1, 1, 3),
new Point(3, 3, 3, 4),
new Point(1, 2, 3, 5), // 与points[0]相同
};
int[] result = solver.solve(points);
System.out.println("=== 三维偏序问题结果 ===");
for (int i = 0; i < points.length; i++) {
System.out.printf("点(%d,%d,%d) 的答案: %d%n",
points[i].a, points[i].b, points[i].c, result[i]);
}
// 手动验证
System.out.println("\n=== 手动验证 ===");
for (int i = 0; i < points.length; i++) {
int count = 0;
for (int j = 0; j < points.length; j++) {
if (points[j].a <= points[i].a &&
points[j].b <= points[i].b &&
points[j].c <= points[i].c) {
count++;
}
}
System.out.printf("点%d 暴力验证: %d%n", i, count);
}
// 性能测试
System.out.println("\n=== 性能测试 ===");
int testN = 100000;
Point[] largePoints = new Point[testN];
Random rand = new Random(42);
for (int i = 0; i < testN; i++) {
largePoints[i] = new Point(
rand.nextInt(100000),
rand.nextInt(100000),
rand.nextInt(100000),
i
);
}
long start = System.currentTimeMillis();
solver.solve(largePoints);
long elapsed = System.currentTimeMillis() - start;
System.out.printf("N=%d 的CDQ分治耗时: %d ms%n", testN, elapsed);
}
}
算法扩展：动态逆序对
CDQ分治还可以解决更复杂的问题，如带修改的逆序对计数。核心思想是将”修改”也看作一个维度，通过时间分治将在线问题离线化。
/**
* 使用CDQ分治求解动态逆序对（简化版）
* 将每个操作按时间分治，左侧的修改影响右侧的查询
*/
static class DynamicInversionQuery {
int time; // 时间维度
int pos; // 位置
int val; // 值或查询类型
int type; // 0=修改, 1=查询
long ans; // 查询结果累加器
}
// 将CDQ应用于时间维度，归并时按位置排序，用树状数组维护值维度
// 这是CDQ分治的经典应用之一
复杂度分析
时间复杂度
| 步骤 | 复杂度 | 说明 |
|---|---|---|
| 按a排序 | O(N log N) | 处理第一维 |
| 去重 | O(N) | 统计重复点 |
| c坐标离散化 | O(N log N) | 压缩坐标 |
| CDQ分治 | O(N log² N) | 每层O(N log N)，共log N层 |
| 总复杂度 | O(N log² N) |
空间复杂度
- 点数组：O(N)
- 树状数组：O(N)（离散化后）
- 归并临时数组：O(N)
- 总空间：O(N)
CDQ分治适用场景
CDQ分治特别适合以下类型的问题：
- 多维偏序计数：k维偏序可降至k-1维处理
- 动态区间问题：通过时间分治离线处理修改操作
- 嵌套区间问题：区间包含关系的统计
- 需要降维的DP优化：如某些树形DP的优化
总结
CDQ分治是信息学竞赛中最重要的算法思想之一，其核心在于降维和离线。通过分治将高维问题分解为低维子问题，再配合合适的数据结构（如树状数组、线段树），可以高效解决许多看似需要高维数据结构的复杂问题。掌握CDQ分治，相当于掌握了一把降维打击的利器。
