范围树

范围树

给定平面点集，对矩形区域的查询，报告区域内的所有点。 暴力解法：$O(n)$ 输出敏感？

一维情况：二分查找找到右端点后逐个向前检查，时间复杂度 $O(r+\log n)$ 该思路不容易扩展到高维。

能否用 BBST 解决？ $O(n)$ 时间构造一颗 BBST，查询两个端点，得到两根藤，内侧子树即为所求，同样可以在 $O(\log n+r)$ 时间内完成，空间复杂度为 $O(n)$。

怎么推广到高维？ 先做 x-query，再做 y-query

问题：可能 x-query 几乎命中了所有点，而 y-query 排除了几乎所有点，此时总耗时退化到 $O(n)$

多层搜索树 MLST

x-tree 中每个节点对应一个 y-tree。 查询时，$O(\log n)$ 时间得到 $O(\log n)$ 颗 y-tree，对每颗 y-tree 再做一次 $O(\log n)$ 时间查询，总查询时间为 $O({\log }^{2}n+r)$。

空间复杂度

• 每个点存在 $O(\log n)$ 颗 y-tree 中
• x-tree 中的每层各个节点关联的 y-tree 没有重叠，占用 $O(n)$ 空间 均可推出，总空间复杂度为 $O(n\log n)$

预处理

在自底向上构造 x-tree 时可同时构造 y-tree，合并两个子节点对应的 y-tree，可以先将它们转化为有序数组，进行二路归并，再转为 BBST，时间正比于两个 y-tree 的节点总数，同高度的 y-tree 总共恰好保存了所有节点，因此每层 y-tree 合并只需 $O(n)$ 时间，总时间复杂度为 $O(n\log n)$

更高维度

$d$ 维情况：

• 占用空间 $O(n{\log }^{d-1}n)$
• 构造时间 $O(n{\log }^{d-1}n)$
• 查询时间 $O(r+{\log }^{d}n)$

优化：分散级联

对于最后一维（二维情况下的 y 维度），实际上不需要组织为 BBST，可以简化为一个有序列表。 注意到每次查询中，对于多个 y-tree 的查询的范围是一致的，因此孩子的查询可以复用父亲的查询结果。 找到所有待查询的 x 树中节点的 LCA，在该节点对应的 y 树中花 $O(\log n)$ 查询后其余节点只需 $O(1)$ 时间即可完成查询 该优化只能用于最后一维，可以将查询时间优化到 $O(r+{\log }^{d-1}n)$，而构造时间和占用空间不变