给定空间中的n个点，问每个点有多少个点小于等于自己。
先来分析简单的二维的情况，那么只要将x坐标排序，那么这样的问题就可以划分为两个子问题，，这样的分治有一个特点，即前一个子问题的解决是独立的，而后一个子问题的解决依赖于前一个子问题，即用前一个子问题来解决后一个子问题，而不是合并。 这就是cdq分治。
具体的代码如下。
void cdq(int l, int r){ if(l==r) return; int m = (l+r)>>1; cdq(l,m); cdq(m+1,r); //按y进行排序，那么问题就变成两个y递增的集合， //后一个集合中的每个y在前一个集合中有多少个y小于等于它 sort(a+l,a+m+1,cmp); sort(a+m+1,a+r+1,cmp); int j = l; for(int i=m+1;i<=r;++i){ for(;j<=m;&&a[j].y<=a[i].y;++j); a[i].sum += j - l; } }
而三维的问题由于多了一维，不能使用线性的方法 了。
我们可以用树状数组来维护z这一维，具体的代码如下。
并且最后要注意坐标相等的情况。
第一份代码,因为cdq里面又嵌套了sort，所以时间复杂度是O(n*logn*logn)
#include <stdio.h> #include <math.h> #include <algorithm> #include <iostream> #include <string.h> using namespace std; struct Point{ int x,y,z; int id; int sum; Point(){} Point(int x, int y):x(x),y(y){} bool operator<(const Point&rhs)const{ if(x!=rhs.x) return x < rhs.x; if(y!=rhs.y) return y < rhs.y; return z < rhs.z; } bool operator==(const Point &rhs)const{ return x==rhs.x && y==rhs.y && z==rhs.z; } }; bool cmp(const Point &lhs, const Point &rhs){ if(lhs.y!=rhs.y) return lhs.y <rhs.y; return lhs.z <rhs.z; } const int N = 100000 + 10; Point a[N]; class BIT{ public: int sum[N]; int n; void init(){ n = 100000; memset(sum,0,sizeof(sum)); } int lowbit(int x){ return x & (-x); } int modify(int x, int val){ while(x<=n){ sum[x] += val; x += lowbit(x); } } int getSum(int x){ int ret= 0; while(x>0){ ret += sum[x]; x -= lowbit(x); } return ret; } }bit; void cdq(int l, int r){ if(l==r)return; int m = (l+r)>>1; cdq(l,m); cdq(m+1,r); sort(a+l,a+m+1,cmp); sort(a+m+1,a+r+1,cmp); int j = l; for(int i=m+1;i<=r;++i){ for(;j<=m &&a[j].y<=a[i].y;++j) bit.modify(a[j].z,1); a[i].sum += bit.getSum(a[i].z); } for(int i=l; i<j; ++i) bit.modify(a[i].z,-1); } int ans[N]; int main(){ int t,n; scanf("%d",&t); while(t--){ scanf("%d",&n); for(int i=0;i<n;++i){ scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z); a[i].id = i; a[i].sum=0;} sort(a,a+n); bit.init(); cdq(0,n-1); sort(a,a+n); for(int i=0;i<n;){ int j = i + 1; int tmp = a[i].sum; //分治时，坐标相等的时候， //排在前边的坐标不能使用后边的坐标更新自己，所以要在这里处理一下 for(;j<n &&a[i]==a[j];++j) tmp = max(tmp,a[j].sum); for(int k=i;k<j;++k) ans[a[k].id] = tmp; i = j; } for(int i=0;i<n;++i) printf("%d ",ans[i]); } return 0; }
第二份代码，在cdq分治的最后加入归并排序，是的复杂度变成O(n*logn)
#include <stdio.h> #include <math.h> #include <algorithm> #include <iostream> #include <string.h> using namespace std; struct Point{ int x,y,z; int id; int sum; Point(){} Point(int x, int y):x(x),y(y){} bool operator<(const Point&rhs)const{ if(x!=rhs.x) return x < rhs.x; if(y!=rhs.y) return y < rhs.y; return z < rhs.z; } bool operator==(const Point &rhs)const{ return x==rhs.x && y==rhs.y && z==rhs.z; } }; bool cmp(const Point &lhs, const Point &rhs){ if(lhs.y!=rhs.y) return lhs.y <rhs.y; return lhs.z <rhs.z; } const int N = 100000 + 10; Point a[N]; class BIT{ public: int sum[N]; int n; void init(){ n = 100000; memset(sum,0,sizeof(sum)); } int lowbit(int x){ return x & (-x); } int modify(int x, int val){ while(x<=n){ sum[x] += val; x += lowbit(x); } } int getSum(int x){ int ret= 0; while(x>0){ ret += sum[x]; x -= lowbit(x); } return ret; } }bit; Point tmp[N]; void cdq(int l, int r){ if(l==r)return; int m = (l+r)>>1; cdq(l,m); cdq(m+1,r); //sort(a+l,a+m+1,cmp); //sort(a+m+1,a+r+1,cmp); int j = l; for(int i=m+1;i<=r;++i){ for(;j<=m &&a[j].y<=a[i].y;++j) bit.modify(a[j].z,1); a[i].sum += bit.getSum(a[i].z); } for(int i=l; i<j; ++i) bit.modify(a[i].z,-1); //归并排序， 这样就不需要上面的sort了 int i = l ; j = m+1; for(int k=l;k<=r;++k){ if(i>m) tmp[k] = a[j++]; else if(j>r) tmp[k] = a[i++]; else if(a[i].y < a[j].y) tmp[k] = a[i++]; else tmp[k] = a[j++]; } for(int k=l;k<=r;++k) a[k] = tmp[k]; } int ans[N]; int main(){ int t,n; scanf("%d",&t); while(t--){ scanf("%d",&n); for(int i=0;i<n;++i){ scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z); a[i].id = i; a[i].sum=0;} sort(a,a+n); bit.init(); cdq(0,n-1); sort(a,a+n); for(int i=0;i<n;){ int j = i + 1; int tmp = a[i].sum; //分治时，坐标相等的时候， //排在前边的坐标不能使用后边的坐标更新自己，所以要在这里处理一下 for(;j<n &&a[i]==a[j];++j) tmp = max(tmp,a[j].sum); for(int k=i;k<j;++k) ans[a[k].id] = tmp; i = j; } for(int i=0;i<n;++i) printf("%d ",ans[i]); } return 0; }
具体算法流程如下：
1.将整个操作序列分为两个长度相等的部分（分）
2.递归处理前一部分的子问题（治1）
3.计算前一部分的子问题中的修改操作对后一部分子问题的影响（治2）
4.递归处理后一部分子问题（治3）
而且如果需要分治完后数据要求有序，那么就可以在分治的最后加入归并排序等手段。
何时使用cdq分治：①如果一个问题的解决需要去循环判断，且这样的问题有很多， 那么就看看能不能分治，减少计算量，从小减小复杂度。