数据结构入门8—K-D Tree

k-d树是一种分割k维数据空间的数据结构。主要应用于多维空间关键数据的搜索（如：范围搜索和最近邻搜索）。K-D树是二进制空间分割树的特殊的情况。

以上来自百度百科。

其实就是一颗二叉树，用于处理多维空间问题，假如有三维，这棵树在第一层以x坐标来分左右子树，第二层以y坐标来分左右子树，第三层z坐标，第四层x坐标，第五层y坐标。。。每次坐标取中位数作为子树的跟是最好的。

它可以用于高效查询距离最近或最远的点，这个博客讲的很好：http://blog.csdn.net/zhjchengfeng5/article/details/7855241

模板题链接

//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=500000+10;
int n,root,k,minans,maxans,ans;
 
struct Node{
    int son[2],minnum[2],maxnum[2],x,y;
}node[maxn];
 
int aa;char cc;
int read() {
    aa=0;cc=getchar();
    while(cc<'0'||cc>'9') cc=getchar();
    while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
    return aa;
}
 
bool cmp(const Node& a,const Node& b) {
    return a.minnum[k]==b.minnum[k]? a.minnum[!k]<b.minnum[!k]:a.minnum[k]<b.minnum[k];
}
 
void pu(int pos) {
    int l=node[pos].son[0],r=node[pos].son[1];
    for(int p=0;p<=1;++p) {
        if(l) {
            node[pos].minnum[p]=min(node[l].minnum[p],node[pos].minnum[p]);
            node[pos].maxnum[p]=max(node[l].maxnum[p],node[pos].maxnum[p]);
        }
        if(r) {
            node[pos].minnum[p]=min(node[r].minnum[p],node[pos].minnum[p]);
            node[pos].maxnum[p]=max(node[r].maxnum[p],node[pos].maxnum[p]);
        }
    }
}
 
int bld(int l,int r,int d) {
    if(l>r) return 0;
    int mid=(l+r)>>1; k=d&1;
    nth_element(node+l,node+mid,node+r+1,cmp);
    node[mid].son[0]=bld(l,mid-1,d^1);
    node[mid].son[1]=bld(mid+1,r,d^1);
    pu(mid);
    return mid;
}
 
int dis(int x,int y) {
    return abs(node[x].x-node[y].x)+abs(node[x].y-node[y].y);
}
 
int ok1(int pos,int i) {
    int max1=max(node[pos].minnum[0]-node[i].x,0)+max(node[i].x-node[pos].maxnum[0],0);
    int max2=max(node[pos].minnum[1]-node[i].y,0)+max(node[i].y-node[pos].maxnum[1],0);
    return max1+max2;
}
 
int ok2(int pos,int i) {
    int max1=max(abs(node[pos].minnum[0]-node[i].x),abs(node[pos].maxnum[0]-node[i].x));
    int max2=max(abs(node[pos].minnum[1]-node[i].y),abs(node[pos].maxnum[1]-node[i].y));
    return max1+max2;
}
 
void q1(int pos,int i) {
    if(!pos) return;
    if(pos!=i) minans=min(minans,dis(pos,i));
    int l= node[pos].son[0]? ok1(node[pos].son[0],i) : (1<<30);
    int r= node[pos].son[1]? ok1(node[pos].son[1],i) : (1<<30);
    if(l<r) {
        if(l<minans) q1(node[pos].son[0],i);
        if(r<minans) q1(node[pos].son[1],i);
    }
    else {
        if(r<minans) q1(node[pos].son[1],i);
        if(l<minans) q1(node[pos].son[0],i);
    }
}
 
void q2(int pos,int i) {
    if(!pos) return;
    maxans=max(maxans,dis(pos,i));
    int l= node[pos].son[0]? ok2(node[pos].son[0],i) : 0;
    int r= node[pos].son[1]? ok2(node[pos].son[1],i) : 0;
    if(l>r) {
        if(l>maxans) q2(node[pos].son[0],i);
        if(r>maxans) q2(node[pos].son[1],i);
    }
    else {
        if(r>maxans) q2(node[pos].son[1],i);
        if(l>maxans) q2(node[pos].son[0],i);
    }
}
 
int main() {
    n=read();
    for(int i=1;i<=n;++i) {
        node[i].x=node[i].minnum[0]=node[i].maxnum[0]=read();
        node[i].y=node[i].minnum[1]=node[i].maxnum[1]=read();
    }
    root=bld(1,n,1);
    ans=1e9;
    for(int i=1;i<=n;++i) {
        minans=1<<30;maxans=0;
        q1(root,i);q2(root,i);
        ans=min(ans,maxans-minans);
    }
    printf("%d",ans);
    return 0;
}