CDQ分治详解

CDQ分治是中国计算机科学家陈丹琦（CDQ）提出的一种特殊的分治算法，主要用于解决数据结构中的离线处理问题，特别是在时间序列分析、三维偏序问题等方面有广泛应用。

基本概念

CDQ分治的核心思想是将一个复杂问题分解为更小的子问题，通过特定的合并方式解决这些子问题。

适用问题

CDQ分治常用于解决以下类型的问题：

三维偏序问题
带修改的查询问题
时间序列数据分析

算法框架

典型的CDQ分治框架如下：

划分阶段：按某一维度（通常是时间维度）将问题划分为两个子问题
解决子问题：递归解决左右子问题
合并阶段：处理左子问题对右子问题的影响（关键步骤）

三维偏序问题示例

以经典的三维偏序问题为例（统计满足a[i]<=a[j], b[i]<=b[j], c[i]<=c[j]的对数）：

CPP

void CDQ(int l, int r) {
    if (l == r) return;
  
    int mid = (l + r) >> 1;
    CDQ(l, mid);
    CDQ(mid + 1, r);
  
    // 合并处理
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (b[i] <= b[j]) {
            add(c[i], 1);  // 插入树状数组
            tmp[k++] = i++;
        } else {
            ans[j] += query(c[j]);  // 查询满足条件的数目
            tmp[k++] = j++;
        }
    }
  
    while (i <= mid) {
        add(c[i], 1);
        tmp[k++] = i++;
    }
  
    while (j <= r) {
        ans[j] += query(c[j]);
        tmp[k++] = j++;
    }
  
    // 清空树状数组
    for (i = l; i <= mid; i++) add(c[i], -1);
  
    // 按a排序，供上层递归使用
    for (i = l; i <= r; i++) a[i] = tmp[i];
}

算法复杂度

时间复杂度通常为O(n log² n)，因为在每一层递归中通常需要使用树状数组或线段树等数据结构进行辅助。

优势与局限

优势：

可以将高维问题降维处理
能够有效解决一些复杂时序问题
可以处理离线操作序列

局限：

通常只能解决离线问题
对在线问题的支持有限
实现复杂度较高

CDQ分治在比赛中常用于解决三维偏序等复杂问题，是算法竞赛中的重要技巧之一。

CDQ分治

文章操作