K:K维 D:dimension 维度
网上没找到KDtree在OI和c++方面的详解(可能大佬们都觉得这玩意太简单懒得写？)，累死个人.jpg
KDTree相当于多维的线段树
算法流程
我们要构建一颗二叉树。
信息有多维的时候，每往下一层就换一维进行统计。
第一层：先竖着切过(7,2)
第二层：横着切过(5,4)和(9,6)
第三层：竖着切过(2,3)和(4,7)和(8,1)
注意：切的点是某一侧所有点按照某一维排序后的中位数
求中位数用nth_element(,,);不会用的可以学一下
nth_element(first，kth，end)作用：将第k_th元素放到它该放的位置(排序后的位置)上，其他的数会动，但动完后不一定有序。复杂度O(n)
这样就构造出一个二叉树了。
其他操作都在这个二叉树上进行。
建树的同时记录一下点的范围，以便询问的时候好剪枝
打标记啥的就类似于线段树。
求最值的话需要估价函数和剪枝，可以看一下洛谷的P4169 [Violet]天使玩偶/SJY摆棋子
不太理解的话建议配合下边的模板题+代码理解
时间复杂度
单次操作为\(n^{\frac{k-1}{k}}\)(其中k>=2)
不会证，想证明的看这里
模板题
题
P4631 [APIO2018] Circle selection 选圆圈 题解
【模板】三维偏序（陌上花开） 三维KDTree裸题
P4169 [Violet]天使玩偶/SJY摆棋子需要用到估价函数
用到了求第k大的思想，用一个小根堆，往这个堆里面加入 k 个 极小值，然后将每个元素与堆顶元素比大小，如果大于堆顶元素的话，把堆顶弹出，再把这个元素加入，最后答案就是堆顶。
P4357 [CQOI2016]K 远点对 裸题，思路类似于[十二省联考2019]异或粽子，先记录每个点的最远点对，排好序，取出哪个点就更新哪个点的下一远点对，用KDTree查询
P3769 [CH弱省胡策R2]TATT 裸题，貌似也可以用cdq套cdq来做
P6349 [PA2011]Kangaroos 暂时不会，让我研究研究
京公网安备 11010502036488号