赶脚K-D Tree是一种很实用的数据结构啊~好好学一下~
目前题目中见到的应用都是在二维空间中,所以以下的陈述也是基于二维空间的：
1、做什么的？
假设有若干个二维数据点,数据点位于二维空间内。
k-d树算法就是要确定这些分割空间的分割线。
2、分为哪几部分？
①有关k-d树本身这种数据结构建立的算法
②在建立的k-d树上如何进行最邻近查找的算法。
3、具体介绍：
k-d树是一个二叉树，每个节点表示一个空间范围。
每个节点存储的信息包含为以这个点为根的子树所有的点的矩形的左上角和右下角的坐标。我们在划分结束时更新即可。
建树:节点含义上类似线段树,但建树时有明显不同.2维分别满足BST的属性.
树中节点编号1~n,分别表示按0/1维排序后的排名.
即对于一个节点x,其左子节点编号比x小,右子节点编号比x大
p是辅助数组,每次递归排序,因为每次只需要找"中位数"作为根节点,所以调用nth_element即可
注意!nth_element(p+l,p+mid,p+r+1) +1是虚节点,分清l与1!!!
根据定义,对左右递归时去除mid
所以讲道理kd-tree是比较省空间的,只需要开N即可
插入:根节点递归向下插入.每次插入后pushup更新
相当于线段树动态开点,但动态插入的点的编号不满足上述性质
注意如果有插入操作,空间应该开N+M!
查询:从根节点开始，递归向下查询：
首先用当前节点更新答案，随后看左右子树所对应的矩形，若询问点在矩形外，矩形距离的询问点到这个矩形的最近距离，否则为0.
我们优先选择矩形距离比较小的一侧递归向下询问。询问之后，若另一侧的矩形距离不大于当前的最优解，则再询问另一侧。
这种算法在随机数据上是lg的，但是在构造数据上约是sqrt的。
对估价函数get(int k,int now)的理解：
1、求出询问点now与当前节点k所包含的区域的最小距离。
这个“估计”出来的距离不会比实际距离大。
2、query(int k,int now)时对当前节点k的左右节点分别计算估价函数.
对于每一侧的计算结果来说，
如果这个距离都比ans大,则不需要在该区域寻找更近点。
对于两侧的计算结果,
先对得到距离较小的一侧进行处理,更新ans值,
再用最优情况得到的ans值与次优情况的“估计”值相比较，
可以发现,进入次优的子树的概率会降低,大大减少了总处理次数。
这其实是query()dfs过程中的一个强大剪枝！
例题:2716: [Violet 3]天使玩偶 && 2648: SJY摆棋子
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
using namespace std;
const int N=500000+5;
const int inf=1<<30;
int n,m,rt,D,ans;
struct kdtree{
int l,r;
int d[2];
int mn[2],mx[2];
bool operator <(const kdtree &rhs)const{
return d[D]<rhs.d[D]||(d[D]==rhs.d[D]&&d[D^1]<rhs.d[D^1]);
}
}t[N<<1],p[N],tmp;
int dis(kdtree a,kdtree b)
{return abs(a.d[0]-b.d[0])+abs(a.d[1]-b.d[1]);}
void pushup(int k)
{
int ls=t[k].l,rs=t[k].r;
F(i,0,1){
if(ls){
t[k].mn[i]=min(t[k].mn[i],t[ls].mn[i]);
t[k].mx[i]=max(t[k].mx[i],t[ls].mx[i]);
}
if(rs){
t[k].mn[i]=min(t[k].mn[i],t[rs].mn[i]);
t[k].mx[i]=max(t[k].mx[i],t[rs].mx[i]);
}
}
}
inline int build(int l,int r,int now)
{
D=now;
int mid=(l+r)>>1;
nth_element(p+l,p+mid,p+r+1);
t[mid]=p[mid];
F(i,0,1) t[mid].mn[i]=t[mid].mx[i]=t[mid].d[i];
if (l<mid) t[mid].l=build(l,mid-1,now^1);
if (mid<r) t[mid].r=build(mid+1,r,now^1);
pushup(mid);
return mid;
}
int get(int k,kdtree x)//这就是"估价函数"啦~
{
int res=0;
F(i,0,1) res+=max(0,t[k].mn[i]-x.d[i]);
F(i,0,1) res+=max(0,x.d[i]-t[k].mx[i]);
return res;
}
void insert(int k,int now)
{
if(tmp.d[now]>=t[k].d[now]){//右侧
if(t[k].r) insert(t[k].r,now^1);
else{
t[k].r=++n;t[n]=tmp;
F(i,0,1) t[n].mn[i]=t[n].mx[i]=t[n].d[i];
}
}else{
if(t[k].l) insert(t[k].l,now^1);
else{
t[k].l=++n;t[n]=tmp;
F(i,0,1) t[n].mn[i]=t[n].mx[i]=t[n].d[i];
}
}
pushup(k);
}
void query(int k,int now)
{
int dl=inf,dr=inf;
int d=dis(t[k],tmp);
ans=min(ans,d);
if(t[k].l) dl=get(t[k].l,tmp);//注意要判断
if(t[k].r) dr=get(t[k].r,tmp);
if(dl<dr){
if(dl<ans) query(t[k].l,now^1);
if(dr<ans) query(t[k].r,now^1);
}else{
if(dr<ans) query(t[k].r,now^1);
if(dl<ans) query(t[k].l,now^1);
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("sjy.in", "r", stdin);
#endif
scanf("%d%d",&n,&m);
F(i,1,n){
p[i].l=p[i].r=0;
scanf("%d%d",&p[i].d[0],&p[i].d[1]);
}
rt=build(1,n,0);
tmp.l=tmp.r=0;
while(m--){
int typ;
scanf("%d%d%d",&typ,&tmp.d[0],&tmp.d[1]);
if(typ==1) insert(rt,0);
else{
ans=inf;
query(rt,0);
printf("%d\n",ans);
}
}
return 0;
}
细节补充:
1、找第k大元素nth_element()需要cmp()
2维情况下,以数据方差大的那一维作为第一关键字排序
维数较多时,只需要判断这一维大小即可.
2、根据实测发现，kd树的两种建树方式，即按照方差较大的维度分开（建树常数大）
或者每一位轮换分割（询问常数大），后者更快也更好些，以后就果断写第二种了。
评论 (0)
