KDT学习笔记

· · 个人记录

KDT的定义与构建

KDT类似二叉搜索树，但可以检索k维的数据

树上每个节点有以下几个域：

左右儿子；当前节点所代表的向量；当前节点划分的维度

类似线段树的建树过程，每次建树的区间减半

众所周知，向量是无法比较大小的，所以每一次划分只能够针对其中一个维度来进行

有两种选择维度的方式：

轮换划分：每一个维度轮着进行

方差划分：优先划分方差较大的维度

因为一般情况下，我们都只是用KDT来维护二维平面，所以用方差划分来实现并不复杂。感性上理解，方差划分应该是要比轮换划分要好一点的，因为方差越大说明这一维的离散程度越大，及时划分肯定更优

因为每一维本身并没有顺序，所以还要找到中位数，用nth_element实现即可

一些复杂度的证明

最重要的一个：超平面经过的区域个数为O(n^{1-\frac{1}{k}})

其实也类似线段树，一直走到一个完全被询问区间包含的区域就可以直接返回了

为了支持查询，每个节点还要记录其子树内每一维的最大最小值（即维护这个节点管辖的超平面）

KDT有两种写法：一种是线段树的叶子式，一种是二叉搜索树的节点式

上面说的都是线段树的写法，这种写法较为简洁且细节少，但不资瓷插入和删除，或者毒瘤出题人强制在线，这时只能用二叉搜索树

如果不是强制需要二叉搜索树，还是建议用线段树的写法，复杂度比较有保证且常数小

众所周知，二叉搜索树可以被卡到一条链，有两种解决办法：随机打乱插入顺序（但仍然要离线），用替罪羊树重构

就是在插入的时候，如果某个节点\alpha \times size[p]\leq \max(size[lson],size[rson])

就重构这一棵树，一般情况下\alpha取[0.6,0.8]，具体分析看yyc博客

还有一种定期重构的方式，大概就是每\sqrt{n}\log n重构整一棵树，表现得挺好

KDT的应用

CF44G Shooting Gallery

题意：有若干个矩形，每个矩形有一个高度

然后有若干次射击，每次射击会射到包含这个节点且高度最小的矩形，然后这个矩形就会被摧毁

输出每次射击射到的矩形，或指出未射中

不妨先考虑一维的情况：

最直接的想法就是维护用数据结构去维护每一个矩形（这里就是一条线），要支持查询和删除，可以用线段树来维护

但有可能一个矩形（一条线）覆盖的区间是相同的，但是长度不同，所以线段树上每个节点还要开一个set来维护

那么二维情况下，就需要一个四分树（或线段树套线段树）套set，三个log的感人复杂度

那不妨反过来考虑，考虑每个矩形能够匹配哪些射击

很容易想到，把矩形按照高度排序，依次处理每一个矩形。那么只需要查询这个矩形中编号最小的射击点并将其删除即可

具体的，将射击点构造KDT，维护子树内最小没有被删除的节点，每次区间询问完后单点修改即可

[CQOI2016]K 远点对

非常暴力的做法：首先对所有的点建立KDT，然后枚举每个点在KDT中查询更新答案

具体的：建立一棵小根堆维护已知的前2k大距离（因为我们算的点对是有序的）。设当前遍历到KDT的某一个节点p

如果枚举的点到p子树内所有节点的最大距离大于堆顶，那么子树内就有可能存在答案所以要递归下去

这里的最大距离，只需维护minx,miny,maxx,maxy就可以算了

这里的最大距离和上面的如果res\leq val[p]都是用到了估价函数的思想来剪枝，并且都用到了判断先走哪个子树的技巧，因为KDT本质上就是一个暴力

注意最大值和最小值的估价函数是不一样的

最大距离的估价函数和平面的四个端点都算一遍就行了，最小距离的估计函数则要和四条边算一下，并且在平面内则是0

既然KDT可以写成线段树的样子，那么就也能像线段树一样维护乱七八糟的标记

上面三道题主要是用来认识KDT的写法以及基本的应用，下面是两道毒瘤题

[NOI2019] 弹跳

一维的情况就是裸的线段树建图，二维的话考虑用KDT来优化建图

注意到这里只有一个点连向区间的操作，所以只需要对入点建立KDT，然后连边从叶子跳到上面连就行了

这样空间复杂度O(m\sqrt{m})，直接写理论上有88分，我得了84分评测记录

然后想了一个优化，不知道为什么只能起到负优化的作用：

因为边数比点数大，所以一个点连向某个区间可能不止一条边，只取边权最小的那一条就行了

不过想到的另外一个优化还是可以过的，就是我们要跑dijkstra但不用真的把边建出来，因为每个点到哪些边都是确定的，所以dijkstra的时候判断当前节点是否是叶子节点，不是的话就往下一层更新，是的话就放到kdt上递归松弛

但这样复杂度其实是不对的，每次从叶子节点的查询需要O(\sqrt{n}\log n)，但是没有被卡掉

更正确的做法，思考dijkstra的松弛过程：找到距离最小的点；把它拿出来更新其他的点；把它删掉

上面三个过程都可以直接用kdt实现，时间复杂度就是严格的O(m\sqrt{n})了

P4848 崂山白花蛇草水

一句话题意：带插入求平面第k大，强制在线

套路的，求k大先二分这个权值，然后找比它小的数量

因为还有插入，所以考虑在线段树上二分，那么只需要在线段树每个节点都开一个KDT来维护平面就行了

注意重构的写法啊！排序不要排错数组了，也不要写错了