给定空间中的n个点，问每个点有多少个点小于等于自己。
先来分析简单的二维的情况，那么只要将x坐标排序，那么这样的问题就可以划分为两个子问题，，这样的分治有一个特点，即前一个子问题的解决是独立的，而后一个子问题的解决依赖于前一个子问题，即用前一个子问题来解决后一个子问题，而不是合并。 这就是cdq分治。
具体的代码如下。
void cdq(int l, int r){
if(l==r) return;
int m = (l+r)>>;
cdq(l,m);
cdq(m+,r);
//按y进行排序，那么问题就变成两个y递增的集合，
//后一个集合中的每个y在前一个集合中有多少个y小于等于它
sort(a+l,a+m+,cmp);
sort(a+m+,a+r+,cmp);
int j = l;
for(int i=m+;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 = + ;
Point a[N];
class BIT{
public:
int sum[N];
int n;
void init(){
n = ;
memset(sum,,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= ;
while(x>){
ret += sum[x];
x -= lowbit(x);
}
return ret;
}
}bit; void cdq(int l, int r){
if(l==r)return;
int m = (l+r)>>;
cdq(l,m);
cdq(m+,r);
sort(a+l,a+m+,cmp);
sort(a+m+,a+r+,cmp);
int j = l;
for(int i=m+;i<=r;++i){
for(;j<=m &&a[j].y<=a[i].y;++j)
bit.modify(a[j].z,);
a[i].sum += bit.getSum(a[i].z);
}
for(int i=l; i<j; ++i)
bit.modify(a[i].z,-); } int ans[N];
int main(){
int t,n;
scanf("%d",&t);
while(t--){ scanf("%d",&n);
for(int i=;i<n;++i){ scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z); a[i].id = i; a[i].sum=;}
sort(a,a+n);
bit.init();
cdq(,n-);
sort(a,a+n);
for(int i=;i<n;){
int j = i + ;
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=;i<n;++i)
printf("%d\n",ans[i]);
}
return ;
}
第二份代码，在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 = + ;
Point a[N];
class BIT{
public:
int sum[N];
int n;
void init(){
n = ;
memset(sum,,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= ;
while(x>){
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)>>;
cdq(l,m);
cdq(m+,r);
//sort(a+l,a+m+1,cmp);
//sort(a+m+1,a+r+1,cmp);
int j = l;
for(int i=m+;i<=r;++i){
for(;j<=m &&a[j].y<=a[i].y;++j)
bit.modify(a[j].z,);
a[i].sum += bit.getSum(a[i].z);
}
for(int i=l; i<j; ++i)
bit.modify(a[i].z,-); //归并排序， 这样就不需要上面的sort了
int i = l ;
j = m+;
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=;i<n;++i){ scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z); a[i].id = i; a[i].sum=;}
sort(a,a+n);
bit.init();
cdq(,n-);
sort(a,a+n);
for(int i=;i<n;){
int j = i + ;
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=;i<n;++i)
printf("%d\n",ans[i]);
}
return ;
}
具体算法流程如下：
1.将整个操作序列分为两个长度相等的部分（分）
2.递归处理前一部分的子问题（治1）
3.计算前一部分的子问题中的修改操作对后一部分子问题的影响（治2）
4.递归处理后一部分子问题（治3）
而且如果需要分治完后数据要求有序，那么就可以在分治的最后加入归并排序等手段。
何时使用cdq分治：①如果一个问题的解决需要去循环判断，且这样的问题有很多， 那么就看看能不能分治，减少计算量，从小减小复杂度。