KDtree学习笔记
推荐一下这位大佬的博客
最近学习了这个数据结构的一些基本应用，在此做一个小结。
KDtree，就是一种用来处理K维数据的数据结构。它的形态就是一颗平衡树，具体来说，我们通过某一种分类方式，使K维空间中的点构成了一颗树，然后我们可以用它来进行高效的搜索剪枝其实就是暴力。那么这种分类方式是什么呢？我们采取比较某一维的坐标大小，并且顺次转换比较的维度，复杂度是(O(n imes n^{frac{k-1}{k}}))，看代码吧。
代码
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define N 1000005
#define lc c[u][0]
#define rc c[u][1]
#define mid ((l+r)>>1)
using namespace std;
inline int In(){
char c=getchar(); int x=0,ft=1;
for(;c<'0'||c>'9';c=getchar()) if(c=='-') ft=-1;
for(;c>='0'&&c<='9';c=getchar()) x=x*10+c-'0';
return x*ft;
}
const int INF=2e9; const double alpha=0.75;
int n,m,rt=0,T_tot,ans,nth_dir,cnt=0,S_top=0;
int mn[N][2],mx[N][2],c[N][2],S[N],sz[N];
struct Point{
int pos[2];
int& operator [] (int x){ return pos[x]; }
}a[N],p[N],Poi;
inline int min(int a,int b){ return a<b?a:b; }
inline int max(int a,int b){ return a>b?a:b; }
inline int abs(int x){ return x>0?x:-x; }
inline void Reset(int u,Point P){
p[u]=P; sz[u]=1; lc=rc=0;
mn[u][0]=mx[u][0]=P[0];
mn[u][1]=mx[u][1]=P[1];
}
inline int newnode(Point P){
int u=S_top?S[S_top--]:++T_tot;
Reset(u,P); return u;
}
inline void Update(int u,int v){
mn[u][0]=min(mn[v][0],mn[u][0]); mn[u][1]=min(mn[v][1],mn[u][1]);
mx[u][0]=max(mx[v][0],mx[u][0]); mx[u][1]=max(mx[v][1],mx[u][1]);
}
inline void PushUp(int u){
sz[u]=sz[lc]+sz[rc]+1;
if(lc) Update(u,lc); if(rc) Update(u,rc);
}
inline void Modify(int u){
mn[u][0]=mx[u][0]=p[u][0]; mn[u][1]=mx[u][1]=p[u][1];
}
inline bool cmp(Point a,Point b){ return a[nth_dir]<b[nth_dir]; }
int Build(int l,int r,int dir){
nth_dir=dir; nth_element(a+l,a+mid,a+r+1,cmp);
int u=newnode(a[mid]);
if(l<mid) lc=Build(l,mid-1,dir^1);
if(r>mid) rc=Build(mid+1,r,dir^1);
PushUp(u); return u;
}
void dfs(int u){
if(lc) dfs(lc);
a[++cnt]=p[u]; S[++S_top]=u;
if(rc) dfs(rc);
}
void check(int& u,int dir){
if(max(sz[lc],sz[rc])>sz[u]*alpha)
cnt=0,dfs(u),u=Build(1,cnt,dir);
}
void insert(int& u,Point P,int dir){
if(!u){ u=++T_tot; p[u]=P; Modify(u); return; }
if(P[dir]>=p[u][dir]) insert(rc,P,dir^1);
else insert(lc,P,dir^1); PushUp(u); check(u,dir);
}
/* this function get the distace from
the point P to the cube made up of all points
that belong to Node u */
/* if the point P is in the area divided by Node u
this function will return 0 */
inline int Mind(int u,Point P){
int tmp=0;
tmp+=max(0,mn[u][0]-P[0]); tmp+=max(0,mn[u][1]-P[1]);
tmp+=max(0,P[0]-mx[u][0]); tmp+=max(0,P[1]-mx[u][1]);
return tmp;
}
inline int dist(Point a,Point b){ return abs(a[0]-b[0])+abs(a[1]-b[1]); }
void Query(int u,Point P){
ans=min(ans,dist(p[u],P)); int d_l=INF,d_r=INF;
if(lc) d_l=Mind(lc,P); if(rc) d_r=Mind(rc,P);
if(d_l<d_r){ if(d_l<ans) Query(lc,P); if(d_r<ans) Query(rc,P); }
else{ if(d_r<ans) Query(rc,P); if(d_l<ans) Query(lc,P); }
}
int main(){
n=In(); m=In();
for(int i=1;i<=n;++i) a[i][0]=In(),a[i][1]=In();
rt=Build(1,n,1);
for(int i=1,op,x,y;i<=m;++i){
op=In(); Poi[0]=In(); Poi[1]=In();
if(op==1) insert(rt,Poi,1);
if(op==2) ans=INF,Query(rt,Poi),printf("%d
",ans);
}
return 0;
}
个人认为KDtree主要不同的地方在于剪枝的估价函数，它可以处理如下问题：
1.曼哈顿距离最近（远）点对。
2.欧几里得距离最近（远）点对。
3.矩阵上的查询操作。
这就是变一变估价函数的事，如果不知道，可以去这看一看。
注意到很多时候我们并不能提前将KDtree离线建好，而是需要动态插入，这样可能会导致KDtree形态不平衡，从而效率下降。我们考虑借鉴替罪羊树的思想，设置平衡因子，当一颗子树不符合要求时，就重建，这就是上面代码的check函数。
2019.04.09upd：注意暴力重构有一个小技巧，就是下传一个祖先节点是否需要重构，如果是，则该节点不需要重构，这样可以优化一大部分常数。
例题
模板题，查询平面上曼哈顿距离最近点对，但最好写动态插入版本的，代码其实就是上面那份。
考虑通过对第一维排序获得一个顺序，然后依次扫描，每一次在符合条件的矩形中取最大值转移，再将自己插入到KDtree里面即可，代码略。
例3.Luogu4148简单题
模板题。考虑维护每一个节点它管辖的子树范围，然后与当前查询范围比较，若被包含，直接返回子树总和，若无交集，返回，否则判断当前节点贡献，然后递归查询左右子树即可，代码略。
博主的做法是维护一个大小为K的(Set)，然后搜索剪枝即可，代码略。