声明
本篇博客只讲解二维的KD-tree，但是二维和多维是互通的，看的人应该可以自通吧。
概念
k-d树（k-dimensional树的简称），是一种分割k维数据空间的数据结构。主要应用于多维空间关键数据的搜索（如：范围搜索和最近邻搜索）。K-D树是二进制空间分割树的特殊的情况。（摘自百度百科）
直接看概念显然看不懂，我们先看看二维的KD-tree长什么样子吧。触摸板画的。。
这里有几个点，我们要建树。
先找出按x排序后最中间的点，从中间分开
这样有什么用呢，你要查询一个点在哪个位置的时候，看看它在哪一边，是不是就直接减掉了一半的点。
然后继续分下去就好了。
操作（二维KD-tree）
构造：
inline int rebuild(int l,int r,int dd){
int mid=l+r>>1;D=dd;
nth_element(a+l+1,a+mid+1,a+r+1);
a[mid].mix[0]=a[mid].mx[0]=a[mid].d[0],
a[mid].mix[1]=a[mid].mx[1]=a[mid].d[1],
a[mid].sum=a[mid].v;
if(l!=mid) a[mid].l=rebuild(l,mid-1,dd^1);
else a[mid].l=0;
if(r!=mid) a[mid].r=rebuild(mid+1,r,dd^1);
else a[mid].r=0;
if(a[mid].l) up(mid,a[mid].l);
if(a[mid].r) up(mid,a[mid].r);
return mid;
}对于每个节点，我们要维护它这个子树中x和y的最大最小值，用以估计它大致是怎样的一个矩阵，在查询时可以用于优化。
插入：
void insert(int k){
int s=root;D=0;
if(!s){
root=k;return ;
}
while(1){
up(s,k);
if(a[k].d[D]<=a[s].d[D]){
if(!a[s].l){
a[s].l=k;break;
}
s=a[s].l;
}
else{
if(!a[s].r){
a[s].r=k;break;
}
s=a[s].r;
}
D^=1;
}
return ;
}这样插不是就不平衡了吗。。所以一些题目中要定期重构KD-tree
删除：打懒标记，定时重构
查询：具体操作要看题面
例题
来看一道简单题（bzoj4066）
Description
你有一个N*N的棋盘，每个格子内有一个整数，初始时的时候全部为0，现在需要维护两种操作：
命令
参数限制
内容
1 x y A
1<=x,y<=N，A是正整数
将格子x,y里的数字加上A
2 x1 y1 x2 y2
1<=x1<= x2<=N
1<=y1<= y2<=N
输出x1 y1 x2 y2这个矩形内的数字和
3
无
终止程序
Input
输入文件第一行一个正整数N。
接下来每行一个操作。每条命令除第一个数字之外，
均要异或上一次输出的答案last_ans，初始时last_ans=0。
Output
对于每个2操作，输出一个对应的答案。
Sample Input
4
1 2 3 3
2 1 1 3 3
1 1 1 1
2 1 1 0 7
3
Sample Output
3
5
HINT
数据规模和约定
1<=N<=500000,操作数不超过200000个，内存限制20M，保证答案在int范围内并且解码之后数据仍合法。
样例解释见OJ2683
新加数据一组，但未重测—-2015.05.24
Source
By wjy1998
这题与BZOJ2683题面一样，但是这题强制在线，所以要考虑用KD-tree来做。
操作1直接insert，但是要隔一段时间重构一下。
操作2就查询下去，如果整个子树都在矩阵内就直接加上去。
代码
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,D,root,lor,x1,x2,y1,y2,tot,last_ans;
inline int read(void){
int a=0,f=1;static char c;
while((c=getchar())<'0'||c>'9')c=='-'?f=-1:0;
while(c>='0'&&c<='9')a=a*10+c-'0',c=getchar();
return a*f;
}
struct Y{
int d[2],mix[2],mx[2],sum,l,r,v;
inline bool operator <(const Y&a) const{
return d[D]<a.d[D];
}
}a[200002];
inline void up(int k,int s){
a[k].mix[0]=min(a[k].mix[0],a[s].mix[0]),
a[k].mix[1]=min(a[k].mix[1],a[s].mix[1]),
a[k].mx[0]=max(a[k].mx[0],a[s].mx[0]),
a[k].mx[1]=max(a[k].mx[1],a[s].mx[1]),
a[k].sum+=a[s].sum;
return ;
}
void insert(int k){
int s=root;D=0;
if(!s){
root=k;
return ;
}
while(1){
up(s,k);
if(a[k].d[D]<=a[s].d[D]){if(!a[s].l){a[s].l=k;break;}s=a[s].l;}
else {if(!a[s].r){a[s].r=k;break;}s=a[s].r;}
D^=1;
}
return ;
}
inline int query(int now){
if(!now) return 0;
if(x1<=a[now].mix[0]&&x2>=a[now].mx[0]&&y1<=a[now].mix[1]&&y2>=a[now].mx[1]) return a[now].sum;
if(x1>a[now].mx[0]||x2<a[now].mix[0]||y1>a[now].mx[1]||y2<a[now].mix[1]) return 0;
if(x1<=a[now].d[0]&&x2>=a[now].d[0]&&y1<=a[now].d[1]&&y2>=a[now].d[1]) return a[now].v+query(a[now].l)+query(a[now].r);
return query(a[now].l)+query(a[now].r);
}
inline int rebuild(int l,int r,int dd){
int mid=l+r>>1;D=dd;
nth_element(a+l+1,a+mid+1,a+r+1);
a[mid].mix[0]=a[mid].mx[0]=a[mid].d[0],
a[mid].mix[1]=a[mid].mx[1]=a[mid].d[1],
a[mid].sum=a[mid].v;
if(l!=mid) a[mid].l=rebuild(l,mid-1,dd^1);
else a[mid].l=0;
if(r!=mid) a[mid].r=rebuild(mid+1,r,dd^1);
else a[mid].r=0;
if(a[mid].l) up(mid,a[mid].l);
if(a[mid].r) up(mid,a[mid].r);
return mid;
}
int main(void){
register int i;
n=read();
while(1){
m=read();
if(m==3)
break;
if(m==1){
a[++tot].d[0]=read()^last_ans,
a[tot].d[1]=read()^last_ans,
a[tot].v=a[tot].sum=read()^last_ans,
a[tot].mix[0]=a[tot].mx[0]=a[tot].d[0],
a[tot].mix[1]=a[tot].mx[1]=a[tot].d[1];
insert(tot);
++lor;
if(lor==10000){
root=rebuild(1,tot,0);
lor=0;
}
}
if(m==2)
x1=read()^last_ans,
y1=read()^last_ans,
x2=read()^last_ans,
y2=read()^last_ans,
printf("%d\n",last_ans=query(root));
}
return 0;
}