不打算讲定义这类的东西
对这玩意儿的理解大概就是一个玄学暴力叭...
如果题目有多维限制而且又很懒不想写什么CDQ啊树套树啊的话就可以无脑上KDTree
然后KDTree可以干的事比较杂，大概可以分成下面几类：
- 求K维空间最近邻点 这大概就是KDTree最开始发明出来要干的事情吧 可以求曼哈顿距离，欧几里得距离的最近/远点。具体需要通过一个类似于A*中的估价函数去实现。假如说当前搜到的最近距离是 \(ans\)，在KDTree上的 \(x\) 点。那我们需要对点 \(x\) 的左右子树进行一个估价来决定是否进入。假设要求曼哈顿距离最近点，对左子树 \(ls\) 进行估价。我们在每个节点额外维护四个值，表示该点及其子树中 x/y 坐标的最大/小值（实际上就是每个点维护一个矩形区域）。然后我们就可以进行估价了。为了不影响正确性，估价的原则是 估算答案 >= 真实答案，所以不妨将估算答案当作查询点到左子树维护的矩形区域的四个角的曼哈顿距离的最大值。估价后优先进入价值大的子树（因为可能会更优）。
- 对K维空间某个区域求和 嗯这个操作很像线段树 就是进入一个节点之后判断 如果该节点维护的矩形区域被询问区域完全包含 那就用自身维护好的信息更新答案 如果完全不相交 那就直接return 否则递归进两个子树进行查询 很暴力很暴力的思想 注意如果再带修改或者插入的话，那就需要定期重构。重构的方法有两个，一个是插入节点数到达一定阈值之后重构，另一个是仿照替罪羊树那样，如果某个节点的左右子树不平衡，那就拍扁重构一发。
常见估价：
还是看例题吧
Luogu4169 SJY摆棋子
求二维平面上到一个点的最近点 板子题
Luogu4148 简单题
题意
支持两个操作：单点加，矩形求和 强制在线 空间限制20M
Sol
强制在线所以没法CDQ 20M所以没法树套树
只能KDTree了呜呜呜
Luogu4475 巧克力王国
啊也是板子题不讲了不讲了
Luogu2093 JZPFAR
题意
给定平面上 \(n\) 个点，\(m\) 次询问，每次询问平面上离询问点 \((x,y)\) 第 \(k\) 远的点的编号。\(n\leq 10^5,k\leq 20\)。
Sol
这题还行。
就是在全局维护一个大小为 \(k\) 的小根堆。最开始里面全是 \(0\) 。
在KDTree上找到了一个点，如果该点离询问点的距离 > 堆顶离询问点的距离，那就更新堆。
用最远欧几里得距离对子树估价，如果有可能更新堆顶那就递归进去。
Luogu4357 K远点对
题意
给定平面上 \(n\) 个点，询问欧几里得距离第 \(k\) 远的点对间的距离。
Sol
仿照上题，还是维护一个小根堆
对于每个点去KDTree上找尝试更新答案（就类似于上题的询问
最开始要放 \(2k\) 个 $0 $ 进去，原因是每个点对会被重复统计两遍。最后堆顶就是答案。
BZOJ4154 Generating Synergy
题意
给定一棵以 \(1\) 为根的有根树，初始所有节点颜色为 \(1\)，操作为 将 \(a\) 子树中距离 \(a\) 不超过 \(l\) 的节点颜色染为 \(c\)，或者询问 \(a\) 的颜色。
Sol
观察到每次就是把 \(dfn\in[dfn[a],dfn[a]+sze[a]-1]\land dep\in[dep[a],dep[a]+l]\) 的那些节点染色。把 \(dfn\) 作为第一维，\(dep\) 作为第二维放到二维平面上，这就变成了矩形染色，单点查询的题，KDTree即可。
BZOJ3489 A simple rmq problem
题意
给定长为 \(n\) 的序列和 \(m\) 个询问：在 \([l,r]\) 中找到在区间中只出现一次的数，如果有多个就找价值最大的那个。强制在线。
Sol
设 \(pre[i],suf[i]\) 分别表示 \(i\) 前面（或后面）第一个和 \(i\) 权值相同的位置 。那么询问就是查询 \(pre[i]\in(1,l-1]\land i\in[l,r]\land suf[i]\in[r,n]\) 中最大的 \(val[i]\)。放进三维KDTree中就是裸题了，每次查询一个三维区间即可。
BZOJ3616 War
题意
一共有 \(k\) 个阵营，给定二维平面上的 \(n\) 个炮塔和每个炮塔的攻击范围。一共要进行 \(m\) 轮攻击，每次会随机一个炮塔并攻击所有它能攻击到的除了自己阵营的目标。一个炮塔被攻击并不影响它攻击其它炮塔。问进行 \(m\) 轮之后期望剩下多少个阵营，使得这些阵营所属炮塔全部没有被攻击过。
Sol
首先可以求出对于第 \(i\) 个阵营有多少炮塔能攻击到属于它的炮塔，假设有 \(cnt\) 个，那么该联盟的贡献就是 \(1\cdot (\frac{n-cnt}n)^m\) 。然后问题就变成了对于一个炮塔怎么求多少炮塔会攻击到它。这个东西不是很好求，但是我们每次可以用一个炮塔进行攻击啊，这样不就变成了在KDTree上打标记嘛。再拿bitset随便记一下就好了。