KDT

[KDT](https://www.luogu.com.cn/blog/command-block/kdt-xiao-ji#)（K维树）：一种维护K维点的数据结构。虽然复杂度经常涉及根号，但很难卡满。 主要解决的问题有：由一些低维问题扩展来的高维问题（复杂度可能出现 $O(\lg n) \rightarrow O(\sqrt n)$ 的变化）；cdq不能解决的强制在线问题；配合标记的平面/空间的区域处理问题（其中矩形区域搜索有 $O(\sqrt n)$ 的复杂度）。 以上只涵盖了最普通的应用。解决问题时当然要灵活处理。 各种姿势的学习参见[这篇文章](https://www.luogu.com.cn/blog/command-block/kdt-xiao-ji#)（强烈推荐！！！非常神仙！！） 受到这篇文章的影响，我认为把KDT理解成高维线段树要比高维替罪羊树贴切，实现时也写成线段树的形式更方便。解决问题的时候也可以考虑低维的线段树是如何做的，再扩展成高维。 ### KDT上的搜索 比较玄学，难以估计复杂度。本质上就是搜索+KDT天然的剪枝。对于随机数据表现比较好，而构造过的数据则可能不能剪枝，卡到 $O(n)$。有时并不是正解。 这方面经典的问题是K远/近点对。 [P4357 \[CQOI2016\]K 远点对](https://www.luogu.com.cn/problem/P4357) [P2093 \[国家集训队\]JZPFAR](https://www.luogu.com.cn/problem/P2093) 最近最远点对也可以用KDT。虽然最近最远点对有分治、旋转卡壳这样的优秀做法，但它们的扩展性不如KDT。 [HDU2966 In case of failure](http://acm.hdu.edu.cn/showproblem.php?pid=2966) 搜索的可扩展性很强。欧氏距离可以搜，曼哈顿距离当然也可以搜。 [P4169 \[Violet\]天使玩偶/SJY摆棋子](https://www.luogu.com.cn/problem/P4169) [P2479 \[SDOI2010\]捉迷藏](https://www.luogu.com.cn/problem/P2479) 当然，这种搜索好写也好卡。对于欧氏距离的搜索，只要让点分布在圆周上微扰，在圆心查询就不可避免地 $O(n)$；曼哈顿距离改成正方形应该也可以卡。这时应该考虑一下其他正解，如cdq……才怪呢，暴力能过正经人谁想cdq啊（doge） 随机数据就大胆地搜吧！ [P4475 巧克力王国](https://www.luogu.com.cn/problem/P4475) （请视为数据随机） KDT不能直接维护圆形等其他形状，只能用比他们大的矩形/超长方体包含。为了防止被卡，请充分发扬人类的智慧——随机旋转！ [P4631 \[APIO2018\] Circle selection 选圆圈](https://www.luogu.com.cn/problem/P4631) ### 静态KDT的区间查询 如果把搜索区间定为矩形/超长方体，KDT的复杂度就不再那么玄学了。矩形（超长方体）区间上的查询可以证明是 $O(\sqrt n)$（$O(n^{1-\frac{1}{k}})$ ）的，效率不低。 [P3810 【模板】三维偏序（陌上花开）](https://www.luogu.com.cn/problem/P3810) 对于只有删除没有插入的情况，通常只需要懒惰删除就可以了。 [CF44G Shooting Gallery](https://www.luogu.com.cn/problem/CF44G) 比起把KDT理解成高维替罪羊树，或许理解成高维线段树更合适。看起来它维护的是一系列点，实际上维护的是一系列超长方体。 因此，线段树的区间标记技巧也适用于KDT。 BZOJ4154 Generating Synergy [P6349 \[PA2011\]Kangaroos](https://www.luogu.com.cn/problem/P6349) 再来一道interesting的最短路。 [P5471 \[NOI2019\] 弹跳](https://www.luogu.com.cn/problem/P5471) 先考虑一维的线段树情况会更自然。 [P6783 \[Ynoi2008\] rrusq](https://www.luogu.com.cn/problem/P6783) ### 带有插入的KDT 插入不平衡？拍扁重构！……真的需要么？ KDT对平衡的要求实际上比替罪羊树更苛刻。只要保持 $O(\lg n)$ 的树高，二叉搜索树的操作就是 $O(\lg n)$ 的；但只保持 $O(\lg n)$ 的树高，KDT的查询可不一定是 $O(\sqrt n)$ 的。事实上，根据平衡因子 $\alpha>0.5$ 的选择，KDT矩形查询最坏将满足如下递归式： $T(n) = T(\alpha^2 n) + T(\alpha(1-\alpha)n)+O(1)$ 将稍稍退化，稍差于 $O(\sqrt n)$ ，却也算是够用。 不过，我们有更优秀的方法，也就是根号重构的KDT…… 而且非常好写。$O(n\sqrt{n\lg n})$的[实现](https://www.luogu.com.cn/paste/uhmz03oq)和$O(n\sqrt n+n^\frac{5}{4}\lg n)$的[实现](https://www.luogu.com.cn/paste/g8a40346) [P4148 简单题](https://www.luogu.com.cn/problem/P4148)（验证算法正确性和效率的模板题） [P3769 \[CH弱省胡策R2\]TATT](https://www.luogu.com.cn/problem/P3769) [P4848 崂山白花蛇草水](https://www.luogu.com.cn/problem/P4848) （来份毒瘤树套树！）