（休闲娱乐）如果忘了 KD-Tree 怎么写

· · 休闲·娱乐

给出 n 个二维平面上的整点，m 次操作，包括矩形修改、矩形查询。

下面 n,m 同阶。

做法一

KD-Tree。我忘了。

做法二

考虑按 x 坐标排序后分块，设块长为 B。

块内再按 y 排序，开一个线段树或者别的什么数据结构。

修改的话，整块直接在对应块的线段树上改，散块暴力重构线段树即可，复杂度为 \mathcal O\left(\dfrac nB\log n+B\right)。

查询同理，复杂度一样。取 B=\mathcal O(\sqrt{n\log n}) 有最优复杂度 \mathcal O(n\sqrt{n\log n})。

这也太抽象了。

做法三

先赌一波出题人不会造数据，这个做法是基于随机数据的。

先把坐标离散化，这样每个点的坐标范围都在 [1,n] 之间。

将平面按照 B 为块长分块，这样每个块里面期望只有 \mathcal O\left(\dfrac{B^2}{n}\right) 个点。

然后整块一共有 \mathcal O\left(\dfrac nB\right) 列，就用数据结构修改，散块暴力扫即可，复杂度是 \mathcal O(n\sqrt n\log n) 或者 \mathcal O(n^{5/3}) 的，\log 好像可以放里面？不管了。

这也太抽象了。

这个东西好像可以做一些随机数据并且没有修改的东西，比如说 \mathcal O(n\sqrt n) 半平面 rank，\mathcal O(n\sqrt{n\log n}) 半平面 kth，但空间好像也是对应的？

不知道能不能做袜子那个题，感觉有点难。

做法四

还是老老实实打暴力吧。