K-D Tree

[sshwy]

https://oi-wiki.org/ds/kdt/

OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛

[morris821028]

補充：複雜度分析上，用 sort 的確是比較慢的，但是對於遞迴實作時，我們若採用相同的陣列，則劃分時容易造成部分排序好，此時時間複雜度略低於 nth_element 的。

而使用 nth_element 時，不容易實作出打破等價的代碼，這使得左右子樹皆可能涵蓋中間值，對於需要剪枝的算法可能是一個效能退化的點。

[shrtcl]

最近点对那题 build 函数 l>=r 应该改成 l>r 吧，不然叶子结点有可能没计算到，那题数据比较水

[shrtcl]

说错了当我没说

[skip2004]

kdt重构不应该使用替罪羊树的方法，因为kdt复杂度可以粗略表示为sqrt(2)^dep，而替罪羊树的深度是O(logn)而不是logn，最好的方法是隔约sqrt次操作后重构。当然如果可以离线可以先离线操作建树，这样就避免了插入。

[morris821028]

@skip2004
kdt重构不应该使用替罪羊树的方法，因为kdt复杂度可以粗略表示为sqrt(2)^dep，而替罪羊树的深度是O(logn)而不是logn，最好的方法是隔约sqrt次操作后重构。

替罪羊樹為均攤操作，某一次可能跑比較慢達到整棵樹重建，基本上是不影響整體的需求。而你提供的 sqrt 次操作就重構是局部子樹還是整棵子樹？如果不能保證詢問和插入的數量比例的趨勢，很難給予一個最佳的分析，這可能造成卡在臨界 sqrt 的操作前，不斷地詢問造成單次操作 O(sqrt(n))

[skip2004]

@morris821028 我的方法是隔 sqrt(n) 次操作重构整棵子树，可以证明总复杂度为 nsqrtnlogn。
然而如果你直接使用替罪羊树，在比较强力的数据之下，询问时可以将复杂度卡至 sqrt(2)^dep，而替罪羊树的深度是可以卡到比较大的，比如 1.5logn，这样子复杂度就不再是 sqrt(n) 了，将会是更大。

[morris821028]

@skip2004

替罪羊深度最多為 O(log n) 的，而你每 sqrt(n) 才調整一次，那深度應該就會達到 sqrt(n)。套上相同的 kd tree 搜尋邏輯。如果詢問複雜度是深度的一個函數，要做哪一種詢問才會到你所說的單次 sqrt(2)^dep，而每 sqrt(n) 次調整的確不會遇到這個問題？

[skip2004]

@morris821028

@skip2004

替罪羊深度最多為 O(log n) 的，而你每 sqrt(n) 才調整一次，那深度應該就會達到 sqrt(n)。套上相同的 kd tree 搜尋邏輯。如果詢問複雜度是深度的一個函數，要做哪一種詢問才會到你所說的單次 sqrt(2)^dep，而每 sqrt(n) 次調整的確不會遇到這個問題？

这是一个特殊情况，我们在搜索时，除了新加的点外的复杂度最多是 sqrt(n) 的，而访问每个新加的点最多花费 log(n) 的时间，所以新加的点产生的额外搜索时间不会超过 sqrt(n)log(n)，总的来说总复杂度也不会超过 sqrt(n)log(n)

[Yoshinow2001]

@shrtcl
说错了当我没说

话说我现在也有相同的疑问，为什么l=r的时候return 0也可以哇orz

[myeeye]

似乎可以考虑加入二进制分组等实际复杂度更优的重构策略？

[Cat-shao]

第三十一行 if (l >= r) return 0; 是不是应该为 l > r。
改成 l > r 后照样能 AC 。

[xiaohaowudi]

luogu P1429 平面最近点对（加强版）代码貌似写错了吧？build时候 返回0条件应该是l>r, 不是l>=r，OJ上数据水没有测出来

[Hanghang007]

话说现在存在有题卡替罪羊重构然后放根号重构麻？
有题卡轮换切割放方差切割的麻？
我认为能用kdt解决且k都是一样的，然后加上了剪枝的代码基本都没有题目卡吧。

[JohnAlfnov]

P4357 K远点对 kdt过不去了

[cycyyds]

这个类似替罪羊树的动态加点时间复杂度是假的吧
lxl 的 PPT 图片镇楼:
https://cdn.luogu.com.cn/upload/image_hosting/fxc1qrce.png?x-oss-process=image/resize,m_lfit,h_170,w_225

[clx0226]

捕捉一只cyc,但你这清晰度……

[hhc0001]

那如果真的把KDT和平衡树结合到一起又会怎么样呢？

[hhc0001]

毕竟KDT有很多的性质都源于二叉搜索树（平衡树）？

[qiyuewuyi2333]

为什么构建k-D Tree时，要轮换使用的轴？

You just divide the space by x-axis. But now you have to find those points in the area given by y, such as -1. In this case, the k-D Tree you built thoroughly loses efficacy.

Maybe this case is a little extreme, but it could give us one inspiration: If you just build a k-d Tree by one axis, then you lose the infos in the other dimensions. So we need to alternate the splitting dimension by turns. That also makes the value of info of each dimension balanced.

But you also could say I just use an x-axis to search. Yeah, in this situation, you certainly could just use x-axis to build the tree. But this obviously makes the k-d tree degenerate to balanced search tree. It's no sense. Please think about the reason you use kd-Tree.

[qwqAutomaton]

建树这里好像还可以每次取方差最大的一个维度分割，但是这样不知道会不会有优化（小声