[关闭]
@l1ll5 2018-03-04T12:05:27.000000Z 字数 5753 阅读 2788

K-D tree在信息学竞赛中的我也不知道有什么的应用

by dsfz l1ll5


写在前面的话

由于我忘了讲课的时间,所以这篇是赶工的。
部分复杂度分析的过程可能将 混淆为了常数分析,但是对于 OI 中常见的数据规模,这不会导致复杂度分析时超过一个数量级的误差。(逃...
关于 KDT 的复杂度证明,将在本文的最后附上。


Q&A

Q: KDT是啥我没听说过!
A: KDT是一个常用于骗分的高级数据结构!有志成为 DSM 的同学们都要很好的掌握它哦!

DSM:大傻帽 data structure master

Q:那么,在哪里才能学的到呢?
A:在这里...

此处输入图片的描述


前置技能

  1. 至少掌握一个二叉平衡树的基本操作
  2. 了解 stl 函数 nth_element 的用法和基本原理
  3. 有独立考虑出一道题乱搞做法的能力并愿意去使用它

不会 前置技能 1 的同学可以睡觉去补一下了,不会 前置技能 2 的同学可以假装自己会了。


简介

KDT 中译名为 K-D树 顾名思义,是一个用于维护 维空间内的点的数据结构,这个数据结构是以树的形式实现的。
既然它是一棵树,我们可以从树上的节点下手去考虑它。


节点

KDT 上的一个节点存储了一个 维空间的一部分和一个 维空间点的信息。
为方便称呼,记这个 “ 维空间的一部分 ”为子空间域。
同时,对于每个非叶子节点,都可以视作为用一个超平面将这个 维空间分成了两部分,其中它的左右儿子分别用于维护这个超平面“左面”和“右面”的子空间域的信息。

更直观的,给出一个二维空间划分的例子:(图源百度百科,wiki的图被墙了所以没法渲染...)
此处输入图片的描述
其中,坐标为 的点为这个 2DT 的根节点,它将平面划分为左右两部分,它的左右儿子分别为坐标为 的节点。
对于一个子空间域的信息的维护,即子树信息的维护,因为显然一个节点的儿子们组成了这个节点。

此处输入图片的描述

给出一段作为样例的代码实现,其中 ch[2] 指向这个节点的左右子节点, d[K] 为这个节点在 维空间下的坐标,mn[K] mx[K]记录了这个节点所维护的子空间域在每一维下的左右边界,massage用于存储需要维护的信息。


建树

nth_element:用于在 的时间内查询并定位一个无序序列中的第 大元素,并使得该元素左边的元素都是比它小的,右边的元素都是比它大的。

KDT 是一棵二叉平衡树,经典的构造规则是这样的。

首先选取 维中的第一维作为关键字,排序将平面上的所有节点,选取位于中间的节点将空间切割为两个子空间域,对于两个子空间域,用第二维继续进行上述操作,当某次切割使用了第 维空间后循环地选取第一维作为关键字进行操作。
为例,根节点选择 轴,深度为 的节点选择 轴,深度为 的节点选择 轴,深度为 的节点选择 轴...

构造过程中的排序用 nth_element 以 的实现,对于初始化节点的信息,是 的,显然建树的过程的复杂度是 的,由于 通常较小,显然建树的过程不会成为复杂度的瓶颈。
显然的,我们只需要保存每个节点的信息,所以一棵 KDT 的空间复杂度为

此处给出一个 2DT 的样例代码实现:
此处输入图片的描述

其中, 数组存储初始平面上的节点信息(只有坐标是有效的), 变量 为目前的排序关键字。
每次取中位数建树的目的是为了让两颗子树尽可能平衡。
事实上,循环地取第 维建树也是为了子树尽可能的平衡,比较逗比地,可以每次选择随机的一维划分这个空间,复杂度也是可以保证的...


查询

现在我们考虑实现在这颗 KDT 上的查询操作:

单点查询

简单地查询平面上一个点的点权/到给定点的距离

由于 KDT 是一棵二叉平衡树,所以像遍历平衡树那样去找到查询的节点即可,复杂度显然是的。

最近邻查询( K 近邻查询)

平面上有一些黑点,给定一个白点,查询这些黑点到这个白点的最近曼哈顿/欧几里得/切比雪夫距离。

切比雪夫距离可以简单的转化为曼哈顿距离计算,曼哈顿距离和欧几里得距离的查询是类似的。

暴力的思路是遍历每个节点,计算距离,显然这么做的复杂度是每次 ,没有用到 KDT 优化。

发现 KDT 上的每个节点都维护了一个子空间域,我们可以简单的求出该点到一个子空间域距离的上下界,我们称这一步为估价,由于我们进行近邻查询,此时取下界估价。

实时地记录一个目前答案,对左右子树进行估价,若估价后的下界仍然大于答案,则必定不用进入该子树搜索,否则进入该子树。

若左右子树都需进入,则取下界较小的那个先进入,因为这样更容易更新答案,剪枝更有效。

对于 K 近邻查询,用一个堆维护即可,是常见的套路。

最近邻查询对于随机数据的复杂度是 的。但是对于构造性的数据无法保证稳定性。

矩形查询

平面上有一些点,支持矩形点权修改,矩形点权和查询,矩形点权最值查询,在线。

如果离线的话 CDQ分治 可以优雅的解决此问题。但是我们需要在线做法。
这是一个经典的,可以用二维数据结构较复杂地解决的问题。不过这些做法普遍需要至少 的空间复杂度和 的时间复杂度。
可以在 的空间和 的时间内解决该问题,同时常数相对较小。

考虑暴力:枚举每个节点是否在给定矩形中,判断对答案的贡献系数,显然是 的。
如何使用 KDT 优化呢? 发现如果给定矩形和当前矩形完全无交,则不需要考虑这个节点的子树了,或者如果给定矩形包含了当前矩形,则当前矩形的子树信息可以直接 的统计上去,也不需要进入子树。只有当前矩形和给定矩形有部分交时才需要考虑左右子树。

利用这个剪枝就可以做到最劣单次查询 的复杂度,这是稳定的,是不是灰常神奇啊233。详细的证明将在后面提到

所以我们发现 KDT 可以普遍地替代多数二维数据结构,事实上,对于 维数据结构也是可以简单替代的,在牺牲一点效率(?)的情况下大幅降低了编程复杂度,真是妙啊。


修改

刚刚考虑的都是不存在修改操作的情况,现在我们考虑修改操作会对 KDT 带来哪些影响。

单点修改点权

类似平衡树, 的找到修改节点直接修改信息, 上去即可。

矩形修改点权

用和矩形查询一样的思想剪枝,找到所有包含于修改矩形的节点,用打标记的思想修改即可,每次访问到一个节点都需要下传标记,单次操作的复杂度显然也是 的。

单点删除

类似单点修改,找到这个点,清空信息和其父节点与它的链接即可,

单点插入

可以简单的像单点删除那样去插入一个点,但是问题出现了,插入一个节点的时候我们并没有像建树那样用 nth_element 来保证左右子树尽可能的平衡,也就是说可能存在构造性较高的数据使得我们的 KDT 退化为一条链导致绝大部分操作退化为 , treap 和 splay ,通过旋转树的结构保证平衡,但是显然 KDT 不能这么做,所以普遍采用暴力重构来保证复杂度,常见的实现有两种:

  1. 插入操作超过次数限制 后暴力重建整颗树,则复杂度为 ,合理的
    可以把题 A 掉...常数很大,但优势是代码复杂度很低,写起来很轻松。
  2. 发现上一种看起来太不靠谱了,我们可以采用替罪羊树式的重构方式,即若左右子树大小比例劣于限制 后将这颗子树暴力重构,套用替罪羊树的势能分析可以发现单次插入复杂度为均摊 ,常数一般,实现略麻烦。

此处输入图片的描述

啊,维护靠谱的插入操作的确有点麻烦...


应用

上文提到了 KDT 的几个常见操作,作为一个常用于骗分的高级数据结构, KDT 当然常常被用来解决一些奇奇怪怪的问题啦,下面我们通过几个奇奇怪怪的例题来进一步了解 KDT 。

BZOJ 3489 A simple rmq problem

一句话题意:强制在线询问区间只出现一次的最大的数。
数据范围: , ,

此处输入图片的描述

题解:
记下标为 的这个数上一次出现的位置是 , 下一次出现的位置是 ,每次询问区间为
考虑合法的答案需要满足哪些特征:
首先在区间内:
只出现过一次: ,
这样一个数可以被视作三维空间内一个坐标为 的一个点,其中点权为 ,每次查询一个长方体内点权的 即可。
这个操作用 可以轻松实现,复杂度为 ,编程复杂度很低,只需要

neither 爷说此题由于 一维“接地”了,所以可以排序后用 可持久化树套树 实现。
此处输入图片的描述
我选择 KDT,在实际运行中比很多实现较劣的树套树快。

BZOJ 4605 崂山白花蛇草水

一句话题意:强制在线带插入询问矩形第 大。
数据范围: ,
此处输入图片的描述

题解:
稍有常识的人熟悉数据结构的同学都能看出,询问第 大这个限制可以通过在外层套一棵权值线段树,内层数据结构动态开点来额外耗费 时间解决。
所以单点插入,询问矩形和用 轻松实现即可。
说的容易,你写啊
由于有插入操作,需要替罪羊式的重构,还是不太好写的...
此题实际数据卡掉了绝大多数固定重构的方式,不过实际上可以面向数据编程设置...
时间复杂度 ,空间复杂度

BZOJ 4154 [Ipsc2015]Generating Synergy

一句话题意:给定一棵以 1 为根的有根树,初始所有节点颜色为 1,每次将距离节点 不超过 的子节点染成 ,或询问点 的颜色。
数据范围:
此处输入图片的描述

题解:
震惊,CF EDU Round居然出原题还rated
发现子树内对应 序上的一段连续区间,距离不超过 对应深度的一段连续区间,所以树上的一个点可以转换为坐标为 的二维平面上的一个点。
矩形 cover 和单点查询可以用 kdt 实现,复杂度 ,空间
实际上由于常数小爆踩了neither的差点被卡空间的二维线段树。

上述三题都是 KDT 替代奇怪数据结构的经典例子,相反 KDT 的本职工作——最近邻查询相关的题倒不是很常见...
给出一些练习题,在此不做讲解。

  1. BZOJ [2716/2648] [[Violet 3] 天使玩偶/SJY 摆棋子] 模板题 平面最近邻(曼哈顿距离)查询
  2. BZOJ 1941 [Sdoi2010]Hide and Seek 平面最近/最远邻(曼哈顿距离)查询
  3. BZOJ 3053 The Closest M Points 近邻(欧几里得距离)查询
  4. BZOJ 4066 简单题 强制在线卡空间二维点加权/区间求和(KDT only)

复杂度

需要注意的是, KDT 只能用于矩形查询/修改,对于圆形的查询/修改,可以针对性的构造数据使其退化,但对于随机数据仍有较好的性能。

简单地,我们先考虑二维的情况再进行推广。

证明都是我乱(Y)写(Y)的,写错了请指出,谢谢。

证明两个复杂度:

  1. 矩形查询复杂度
  2. 近邻查询复杂度

矩形查询复杂度证明

不失一般性地,考虑一个如下图的矩形查询。
此处输入图片的描述

这个平面被切割成了若干个小矩形,我们可以将这些矩形分为三类:

  1. 完全不被红色矩形包含的小矩形。
  2. 完全包含于红色矩形的小矩形。
  3. 部分包含于红色矩形的小矩形。

考虑矩形查询的剪枝过程,显然第 1 类会被立刻剪掉,因为毫无贡献。第 2 类也会被减掉,因为答案的贡献是整个子树。所以对答案的复杂度有贡献的只有第三类矩形,记这样的矩形有 个。
更进一步地,若访问一个节点的复杂度为 ,则单次操作的复杂度为

直接考虑 的值是困难的,转化一下,考虑矩形的四条边界分别跨过了多少矩形。
此处输入图片的描述
不失一般性地考虑竖直线的情况,标注出每次平面划分的位置:
此处输入图片的描述
其中绿线为根节点(记deep[root]=1)的第一次划分,蓝线为根节点的直接儿子(deep[x]=2)们的第二次划分。
显然,根节点是必须遍历的,对于左右两儿子,显然维护了右平面的那个儿子会被直接剪枝掉,不需要遍历,则只遍历左儿子节点即可。这次纵向分割减掉了一半的枝条。
下一次分割为蓝线的横向分割,显然无法起到剪枝效果,上下两个子树都需要遍历。
此处输入图片的描述
下一次分割为纵向分割(黄色),可以剪掉一半的枝条。
以此类推地进行下去,显然每次纵向分割(即和竖直线同向)都可以让查询直线只存在两个子树之一。
而对于每次横向分割,两个子树都被贯穿,无法起到剪枝效果。

此处输入图片的描述

形象的看,将会访问所有灰色的节点。所以我们只需要统计灰色的节点个数即可。
不考虑根节点,对于偶数层,访问节点的个数将会翻倍,对于奇数层则不变。
令有 层,显然 ,那么灰点个数
啊,约等于是我懒得算边界情况了,反正数量级没错...

所以一条直线穿过了 个矩形。

此处输入图片的描述
回到这幅图,一个矩形的边框穿过了多少个矩形可以看做是它的边所在的的四条直线穿过了多少个矩形。
显然是也是的,不过由于通常跑不满所以常数较小...
所以矩形查询的复杂度是单次 的。

刚刚考虑了矩形的情况,对于 维的情况可以相似的分析,同样每 维中只有一维可以起到剪枝的效果,式子就不写了。
复杂度为单次 的。

近邻查询复杂度

在写这篇文章以前,我认为近邻查询的复杂度也是 的。不过通过上面的分析可以发现,欧几里得距离和曼哈顿距离近邻查询时,要么查的是一个圆,要么是一个菱形,都无法控制穿过的矩形数目。为此,我查阅了一些资料,发现提到最多的都是近邻查询在随机情况下的复杂度,没有任何资料证明了它的稳定性...

那么我们考虑在 随机情况下 的复杂度:

感性的考虑,如果点是随机分布的,那么一定趋于很均匀的把整个图分成了类似网格图的样子。
这样一次近邻查询只需要走到叶子节点即可,是 的。

不会严格的证明...

此处输入图片的描述

模板题的样例实现可以在我的博客找到。

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注