Cdq分治

Published: April 15, 2019 by Daltao

• Categories:
• algorithm 101

• Tags:

• CDQ分治

CDQ分治

CDQ分治是一种基于分治的解题思路。

假设在三维空间存在点集$P={p_1,p_2,\ldots,p_n}$，对于每个点$p_i=(x_i,y_i,z_i)$，问点集中有多少点落在以$(0,0,0)$与$(x_i,y_i,z_i)$确定的三维矩形中，换言之，有多少点$p_j=(x_j,y_j,z_j)$满足$x_i\leq x_j\land y_i\leq y_j \land z_i\leq z_j$。

最简单的方式是嵌套for循环，时间复杂度为$O(n^2)$。CDQ分治可以以$O(n(\log_2n)^2)$的时间复杂度内解决三维偏序问题。

下面说一下解决的流程。首先我们可以先将点集去重，保证所有顶点都互不重复。之后我们对点集按照$x,y,z$坐标值按照字典序从小到大排序（保证只有左边的点能对右边的点贡献）。之后我们进入分治流程，其中$solve(l,r)$表示计算第$l$到$r$个顶点之间的偏序关系。在完成了$solve(l,m)$和$solve(m+1,r)$后，我们要计算区间$[l,m]$对区间$[m+1,r]$的贡献，由于已知$[l,m]$中的点的$x$值必定小于$[m+1,r]$中的点，因此我们这时候只需要考虑二维偏序的问题。

要解决二维偏序的问题，我们可以对两个区间分别按照y左边进行从小到大排序，之后利用树状数组或线段树记录点数目。这个过程的时间复杂度是$O((r-l+1)\log_2(r-l+1))$。

整体的时间复杂度为$T(n)=2T(\frac{n}{2})+n\log_2n=O(n(log_2n)^2)$。

要解决三维偏序问题，你也可以选择使用线段树套线段树，利用惰性创建结点也可以以$O(n(\log_2n)^2)$的时间复杂度和空间复杂度解决三维偏序问题。但是CDQ分治的时间空间复杂度仅为$O(n)$，要优于线段树套线段树。并且我们还注意到时间复杂度中带有$(\log_2n)^2$，这意味着平衡树的查询更新操作的常数$c$将会变成$c^2$，这时候常数就很重要了，而树状数组的常数是非常小的，比较线段树等其它平衡树优势非常巨大。

void solve(Point[] points, int l, int r)
{
    if(l == r)
    {
        points[l].count += 1;
        return;
    }
    int m = (l + r) / 2;
    solve(points, l, m);
    solve(points, m + 1, r);
    sort(points, l, m);
    sort(points, m + 1, r);
    for(int i = m + 1, j = l; i <= r; i++)
    {
        for(; j <= m && points[j].y <= points[i].y; j++)
        {
            bit.update(points[j].z, 1);
        }
        points[i].count += bit.query(points[i].z);
    }
}