K-D TREE 学习笔记
K-D TREE
一种十分高级的树形结构，可以求各种偏序问题。
参考的资料
浅谈偏序问题与K-D Tree (写的很细，但代码用的是指针。)
OI-WiKi (写的比较清晰，但比较简略)
思路
K-D TREE ，其中k表示的是k维空间，即为一种可以高效处理 k 维空间信息的数据结构。
其实K-D TREE 真的不难，只是不敢学而已。
建树
对于所有点，我们每次选择其中一维，将数据分成两个部分。至于选择哪一维，常用的有两种方案。
-
一是按照选择的维度内部点的分布的差异度最大，即每次选择的切割维度是方差最大的维度
-
还有就是几个维度之间轮着切割。
因为第一种还要计算方差，常数很大，大部分情况用第二种其实已经很好了。当然，如果出题人想要卡你的话，第一种方案还是要会的。
选择了维度后，选出所有点中以当前维排序的中位点。将其作为当前点，再将剩余的点小于的放在左子树，大于的数放在右子树。对于这个操作，我们可以使用 STL 中的函数nth_element。
对于这个函数的使用，其中传4个值，nth_element(l,mid,r,cmp)。其中l，r表示需要排序的区间，mid表示其划分的位置，cmp表示排序方式。
然后就可以按照前面的规则直接建树了。
int build(int l,int r,int lst){
//l表示当前区间的左端点，r表示右端点
//lst表示当前点的父节点是以哪一维分割的，按第一种方法排序
if(l>r)return 0;//因为之前会将mid用掉，是有可能大于的
int mid=(l+r)>>1;
if(l==r){//到达指定的区间
return l;
//返回当前节点，即作为其父节点的子节点
}
if(lst==1){//现在以第二维分，下同
nth_element(s+l,s+mid,s+r+1,cmp2);
//ntn_element 一个科技函数
//能在 O(n) 的时间将小于mid的点放在左边，大于的放在右边
lc[mid]=build(l,mid-1,2);
rc[mid]=build(mid+1,r,2);
}
else{//以第一维分
nth_element(s+l,s+mid,s+r+1,cmp1);
lc[mid]=build(l,mid-1,1);
rc[mid]=build(mid+1,r,1);
}
return mid;//返回当前节点
}查询
其实还有插入，但因为太恶心了，等我了解深入一点再来。
因为 K-D tree 的特性，对于不同的题有不同的查询。第一种关于最近最远点的查询。
最近最远点（邻域查询）
对于最近最远点，可以直接在 K-D tree 上不断往子树递归，每到一个点就计算当前点的答案。但是直接这样做的话就相当于暴力了。所以还需要剪枝。因为对于 K-D tree 来说，每个子树相当于一个 k 维的空间。所以在我们可以存贮这个空间的最大最小点，计算当前点与这颗子树最大可以提供多大的贡献，如果小于的话，就不用去那颗子树了。
void ask(int l,int r,int x){
if(l>r)return ;
int mid=(l+r)>>1;
if(mid!=x)ans=min(ans,dis(s[x].x,s[x].y,s[mid].x,s[mid].y));//不是同一点就更新答案
if(l==r)return ;
double disl=f(x,lc[mid]),disr=f(x,rc[mid]);
//类似于于一种估价函数
//最优化剪枝，求出最优情况下的值。如果任然大于ans
//说明当前节点不可能产生贡献，直接剪枝。
if(disl<ans&&disr<ans){
if(disl<disr){
//启发式搜索，那个跟小先搜那个，虽然可能用处不大
ask(l,mid-1,x);
ask(mid+1,r,x);
}
else{
ask(mid+1,r,x);
ask(l,mid-1,x);
}
}
else{//有不满足条件的，就不用去搜了
if(disl<ans)ask(l,mid-1,x);
if(disr<ans)ask(mid+1,r,x);
}
if(l==r)return ;
}