KD-Tree 学习笔记

建树

1. 如果当前超长方体只有一个点，返回这个点
2. 选择一个维度（轮流）
3. 选择中位数（\(O(n)\)）
4. 递归

应用

• 定理

二维 KDT 中节点代表矩阵与任意一个矩形（边界上）有交的只有 \(O(\sqrt n)\) 个。

证明：

考虑一条直线，与KDT的交集，此层最多有两个，递归得到递归式，然后套主定理。

增删改查

• 查询

1. 单点是否存在 \(O(\log n)\)
2. 矩阵和：递归，只处理相交 \(O(\sqrt n)\)

剪枝：维护子树支撑矩形。

3. 最近邻，\(k\) 近邻 最坏 \(O(n)\)，可以用支撑矩形最优性剪枝。

• 修改

看做线段树，区间就打懒标记

• 插入

找到单点，然后切割喵 \(O(\log n)\)。

• 删除

为了维护树形，打删除懒标记，或者像 BST 一样，找到子树内里当前删除点最近的同维度的点，交换到叶子上面，然后删叶子。

• 重构

1. 暴力
2. 替罪羊重构，维护子节点占当前节点大小的比例，作为不平衡度，定义阈值重构。
3. 根号重构，存储待插入的点，每 \(B\) 次插入重构，修改均摊 \(O(\dfrac nB \log n)\)，查询均摊 \(O(B+\log n)\)，最优 \(O(\sqrt{n\log n}\)。
4. 二进制分组，分成 \(\text{popcount}(n)\) 组 KDT，每次插入合并，均摊 \(O(n\log^2n)\)。

KDT 本质上是维护一些偏序关系，一般我们用矩形去套点。