K-Dtree学习笔记

又一天过去了,cogito学习了一个奇怪的,复杂度并不是很对的算法。

算是填坑。

讲课人zyy太强辣!

k-d树,是一种用来维护多维空间中的点的数据结构。

和树套树相比而言优点是实现简单适合老年oi选手空间较小,出题人不刻意卡的情况下跑得飞快,可以看起来暴力的姿势以优美的期望复杂度实现一些奥妙重重的操作(比如欧几里得距离最小点对。

那么问题来了。

为什么我的kdt常数辣么大!

为什么我的kdt常数辣么大!!

为什么我的kdt常数辣么大!!!

造一颗kdt,我们需要:

•对多维空间的点进行维护。

•每一次选择一个维度将点集划分为两半。

•然后递归处理两个余下的点集。

•这样子会形成一个树性结构。

•每个节点对应一个点。

这样树高就是严格log。

对于类似于最近点对的查询操作期望是sqrt的吧。

毕竟本身也就一暴力。

不会有闲的蛋疼的出题人去卡它。(flag

对于动态加入的话我们需要替罪羊树(我的辣鸡替罪羊由于要回收节点所以常数比朝鲜树还大。

negiizhao传授了我一些人生经验并表示你只要修改指针然后恍然大悟。

这里给出一个插入的函数(常数巨大所以感受一下就可以了)

1
2
3
4
5
6
7
8
9
10
11
12
void put(int d){
if (!sum[d]){
sum[d]=1;p[d].x=x;p[d].y=y;ff[d]=szb^=1;l[d]=r[d]=0;
qwq[d].xl=qwq[d].xr=x;qwq[d].yl=qwq[d].yr=y;
return;
}if (!ff[d]&&x<=p[d].x||ff[d]&&y<=p[d].y){
if (!l[d])l[d]=z[dd--],sum[l[d]]=0;put(l[d]);
}else{
if (!r[d])r[d]=z[dd--],sum[r[d]]=0;put(r[d]);
}pushup(d);
if (max(sum[l[d]],sum[r[d]])*4>=sum[d]*3)rebuild(d);
}

给出一个重构函数(同样感受一下就可以了)

1
2
3
4
5
6
7
8
9
10
11
12
void build(int ll,int rr,int d){
if (ll>rr)return;if (ll==rr){
sum[d]=1;p[d]=a[ll];ff[d]=szb^=1;l[d]=r[d]=0;
qwq[d].xl=qwq[d].xr=a[ll].x;qwq[d].yl=qwq[d].yr=a[ll].y;
return;
}int mid=(ll+rr)>>1;ff[d]=szb^=1;
if (!ff[d])nth_element(a+ll,a+mid,a+rr+1,cmp1);else nth_element(a+ll,a+mid,a+rr+1,cmp2);
qwq[d].xl=qwq[d].xr=p[d].x=a[mid].x;qwq[d].yl=qwq[d].yr=p[d].y=a[mid].y;sum[d]=1;
if (ll<=mid-1)l[d]=z[dd--],build(ll,mid-1,l[d]);else l[d]=0;
if (mid+1<=rr)r[d]=z[dd--],build(mid+1,rr,r[d]);else r[d]=0;
pushup(d);
}

对于查询最近点的操作我们需要在树上暴力(???

加一个(在树上先搜一个更优的子结点然后再搜一个劣一点的结点之类的)然后通过当前最优解减枝就变成期望sqrt了。

二维数点是稳定的sqrt..(虽然我一直觉得这个是log^2,但是在适用范围内没什么区别(雾)

可以用来刷一些特别毒瘤的卡空间题(雾

这东西的空间还是非常优越的和n同级的

具体的复杂度证明不会,当个结论用就可以了(逃

详细的操作就留坑辣,写了题再更

分享到