K-D树实际上是一棵高维二叉搜索树，与普通二叉搜索树不同的是，树中存储的是一些K维数据
普通的二叉搜索树是一维的，当推广到K维后，就是我们的K-D树了
在K-D树中跟二叉搜索树差不多，也是将一个K维的数据与根节点进行比较，然后划分的
这里的比较不是整体的比较，而是选择其中一个维度来进行比较
在K-D树进行划分时，可以每次选择方差最大的属性来划分数据到左右子树
在K-D树的划分中，这个轴的选取很关键，要保证划分后的左右子树尽量平衡
那么很显然选取这个属性的值对应数组的中位数作为pivot
然后是查找了，最邻近查找的算法描述如下
（1）将查询数据Q从根节点开始，按照Q与各个节点的比较结果向下遍历，直到到达叶子节点为止。 到达叶子节点时，计算Q与叶子节点上保存的所有数据之间的距离，记录最小距离对应的数据点， 假设当前最邻近点为p_cur，最小距离记为d_cur （2）进行回溯操作，该操作的目的是找离Q更近的数据点，即在未访问过的分支里，是否还有离Q更近的点 它们的距离小于d_cur
然后一道模板题，BZOJ1941，给出平面上n个点，求距离每个点最大距离减最小距离(不算自己)的最小值
枚举每个点找最近点，最远点更新答案
敲的好累啊！！
1 #include<cstdio> 2 #include<cmath> 3 #include<algorithm> 4 using namespace std; 5 const int INF=1000000000; 6 const int mod=1000000007; 7 int read() 8 { 9 int x=0,f=1;char ch=getchar(); 10 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 11 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 12 return x*f; 13 } 14 int n,F,rt,ans=INF; 15 int x[500005],y[500005]; 16 struct P 17 { 18 int d[2],mn[2],mx[2],l,r; 19 int& operator[](int x) 20 { 21 return d[x]; 22 } 23 friend bool operator<(P a,P b) 24 { 25 return a[F]<b[F]; 26 } 27 friend int dis(P a,P b) 28 { 29 return abs(a[1]-b[1])+abs(a[0]-b[0]); 30 } 31 }p[500005]; 32 struct kdtree 33 { 34 P t[500005],T; 35 int ans; 36 void update(int k) 37 { 38 int l=t[k].l,r=t[k].r; 39 for(int i=0;i<2;i++) 40 { 41 t[k].mn[i]=t[k].mx[i]=t[k][i]; 42 if(l) t[k].mn[i]=min(t[k].mn[i],t[l].mn[i]); 43 if(r) t[k].mn[i]=min(t[k].mn[i],t[r].mn[i]); 44 if(l) t[k].mx[i]=max(t[k].mx[i],t[l].mx[i]); 45 if(r) t[k].mx[i]=max(t[k].mx[i],t[r].mx[i]); 46 } 47 } 48 int build(int l,int r,int now) 49 { 50 F=now; 51 int mid=(l+r)>>1; 52 nth_element(p+l,p+mid,p+r+1); 53 t[mid]=p[mid]; 54 for(int i=0;i<2;i++) 55 t[mid].mn[i]=t[mid].mx[i]=t[mid][i]; 56 if(l<mid) t[mid].l=build(l,mid-1,now^1); 57 if(r>mid) t[mid].r=build(mid+1,r,now^1); 58 update(mid); 59 return mid; 60 } 61 int getmn(P a) 62 { 63 int ans=0; 64 for(int i=0;i<2;i++) 65 { 66 ans+=max(T[i]-a.mx[i],0); 67 ans+=max(a.mn[i]-T[i],0); 68 } 69 return ans; 70 } 71 int getmx(P a) 72 { 73 int ans=0; 74 for(int i=0;i<2;i++) 75 ans+=max(abs(T[i]-a.mx[i]),abs(T[i]-a.mn[i])); 76 return ans; 77 } 78 void querymx(int k) 79 { 80 ans=max(ans,dis(t[k],T)); 81 int l=t[k].l,r=t[k].r,dl=-INF,dr=-INF; 82 if(l) dl=getmx(t[l]);if(r) dr=getmx(t[r]); 83 if(dl>dr) 84 { 85 if(dl>ans)querymx(l); 86 if(dr>ans)querymx(r); 87 } 88 else 89 { 90 if(dr>ans)querymx(r); 91 if(dl>ans)querymx(l); 92 } 93 } 94 void querymn(int k) 95 { 96 int tmp=dis(t[k],T); 97 if(tmp)ans=min(ans,tmp); 98 int l=t[k].l,r=t[k].r,dl=INF,dr=INF; 99 if(l)dl=getmn(t[l]);if(r)dr=getmn(t[r]); 100 if(dl<dr) 101 { 102 if(dl<ans)querymn(l); 103 if(dr<ans)querymn(r); 104 } 105 else 106 { 107 if(dr<ans)querymn(r); 108 if(dl<ans)querymn(l); 109 } 110 } 111 int query(int f,int x,int y) 112 { 113 T[0]=x;T[1]=y; 114 if(f==0)ans=INF,querymn(rt); 115 else ans=-INF,querymx(rt); 116 return ans; 117 } 118 }kdtree; 119 int main() 120 { 121 n=read(); 122 for(int i=1;i<=n;i++) 123 { 124 x[i]=read(),y[i]=read(); 125 p[i][0]=x[i];p[i][1]=y[i]; 126 } 127 rt=kdtree.build(1,n,0); 128 for(int i=1;i<=n;i++) 129 { 130 int mn=kdtree.query(0,x[i],y[i]),mx=kdtree.query(1,x[i],y[i]); 131 ans=min(ans,mx-mn); 132 } 133 printf("%d ",ans); 134 return 0; 135 }