K-D树 专题训练

发布于 2018-01-19  3.83k 次阅读


K-D树,主要可以解决一些在多维空间上带有限制或者查询临近元素的问题。主要思想就是将数据点划分成许多块(二维情况下就是矩形),然后利用估值函数来减小查询涉及到的范围。

这玩意的复杂度不像其他数据结构那么稳定,一般来说,复杂度都是O(logn)级别的,但是查询操作最坏能被卡到O(n^(1-1/k))的复杂度,其中n为数据点数、k为维数。注意,这玩意维护信息的常数比较大,并且减枝也非常重要。

 

BZOJ1941 [Sdoi2010]Hide and Seek

静态查询平面上的点与其他点最大距离与最小距离之差的最小值(曼哈顿距离)。

裸题,建好树后对于每个点都查询最大距离与最小距离就好了,复杂度O(nlogn)。

 

BZOJ2850 巧克力王国

给出静态平面上的n个点,每个点有点权,每次查询a、b、c三个参数,查询满足ax+by<c的点权和。

同样是建出KD树,估值函数搞成上面那个式子,每个点维护子树和,如果区域最大值都小于c,那么直接加上子树和,如果最小值都大于c,那么直接跳出,剩下的情况加单点贡献即可。

 

BZOJ2626 JZPFAR

查询静态平面上距离某点的欧几里德距离k大的点的编号。

开个小根堆,内部维护小于等于k的元素,如果当前区域最大距离都小于堆顶且堆满那么直接返回。最重要的是,优先遍历最大距离比较大的子树,退栈回到当前节点后再判断下一颗子树是否需要访问,这样可以减少非常多的盲目访问。一开始没想到这个减枝,直接T了一半,好毒啊。

 

BZOJ4520 [Cqoi2016]K远点对

和上题一样,但是要查询整个平面上的k远,每次不清空堆即可。

 

BZOJ4605 崂山白花蛇草水

感觉是这里面最毒的。。。

要求支持动态插入,每次查询矩形内点权k大。

一看到K大,显然要树套树,关键是怎么套才能过。一开始写的是KD树在外面,线段树在里面(我也不知道为什么要相信直觉,可能是思想江化吧),采用替罪羊树的写法,当插入不平衡时重建子树,但是每次重建要重新构建线段树(这就是痛点之一),好像时间空间都要炸啊,然后就写了,开开心心地WA+TLE。本地造了组数据,结果2G的电脑MLE了。中午回来换了别人的做法,把权值线段树套在外面,KD树放里面,每个节点只会被放进O(logn)个KD树中,而KD树的空间复杂度是严格O(n)的,所以空间复杂度O(nlogn)有了保障。每次每个KD树进行重建时,对外层的线段树并没有影响,所以减少了对线段树的操作。

比较重要的减枝是,由于我们每次只查右子树线段树的信息,所以插入可以直接忽略左儿子,加上这个优化跑的飞快。

 

BZOJ2648 SJY摆棋子  &&  BZOJ2716 [Violet 3]天使玩偶

动态插点,查询最近点的距离。

感觉有了上一题替罪羊重构思想的影响,这俩题就非常水了。需要注意的是,在重建的build函数中,nth_element()的使用。即使不重载,也不会报错,就因为这个,我的程序完全变成了暴力,甚至比暴力还慢好多,而且还调了好久才找出错。。。

感觉这题我的KD树比CDQ还慢。。。

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974