DSA - 搜索树应用

不在期中考察范围内，鉴于完全没听懂所以抄了一遍 ppt。

区间树

穿刺查询：给定一组区间，对任何点 q_x，筛选出所有包含该点的区间。

考查所有区间的交非空的情形，取公共交点 m，分别依左端点、右端点排序得到区间列 L，R。

不失一般性，取 q_x>m，区间是否被刺中只取决于右端点是否足够靠右。

取出 R 序列由远及近检视，共 O (r + 1)

分治：取所有端点中位点 x_mid，将原有区间组分成三部分。S_left 右端点全在 x 左侧，S_mid 包含 x。

以此构建搜索树，把 S_mid 存放在根节点，S_left 和 S_right 分别交给左右子树。然后递归的划分。

也就是说，对于每个节点，排序自己的所有区间，然后分配左右区间给左右子树。

对于 S_mid 似乎需要在节点内部维护两个列表 L，R。整个树会把所有区间存储 2 遍，所以空间是 O (n)

对于根节点，需要遍历所有 n 个区间；对于每一层，每个节点只需要遍历分配给自己的 S_left 或者 S_right，累计加在一起也就是 n 个区间。

可以在最开始把所有的 2n 个端点排好序，然后每次挑选中间点都是线性的。

于是每一层的时间复杂度都是线性。

树的渐进高度是 logn，最坏情况是根节点只有 1 个区间，左右子树平均分；最好是占有所有区间。

总的时间复杂度 O (nlogn)

如果 q_x 比当前节点的 x_mid 要小，说明当前节点所有区间的右端点在 q_x 右侧，剪枝右子树，同时在 L（已经有序）中顺序查找哪些区间包含 q_x，并在左子树递归。

线段树

对于穿刺查询问题，同一段初级区间的任何位置，穿刺查询结果是相同的。

运用 BBST，叶节点对应每个初级区间 EI，内部节点对应孩子的作用域的并集。可以考虑在每个叶子节点预先记录横跨 EI 的所有区间。但是，如果有 n 个点，会有 O (n) 个 EI，每个区间最坏情况下覆盖 O (n) 个叶子节点，于是空间复杂度在 O (n²)

通过贪心合并，讲原来挂在叶子节点上的区间传递给父亲。兄弟共用一个区间就可以把区间给父亲。对于每个区间，每层最多两个节点相关。（反证，如果有三个连着的必然有兄弟和同一个相关），于是每个区间最多被记录 O (logn) 次，实现 O (nlogn) 的空间复杂度。

为了搭建线段树，需要先把所有端点排序得到 EI，并以所有 EI（没有挂载区间，只是搭建作用域范围）为叶子节点构建完全二叉树。自底向上合并，确定每个节点的作用域。

然后对于每段区间插入到 BBST 上。

如果区间直接覆盖当前节点作用域就存储副本；判断左右子树作用域谁和当前区间相关，递归。

树的每一层最多访问 4 个节点, 2 个递归 2 个储存副本。每段区间插入只需要 O (logn) 时间。

如果发生了 querySegTree (v,q_x)，说明 q_x 一定在 v 的区间作用域内，此时把这个作用域覆盖的所有不同于祖先的区间都在这个点被记录，于是添加这些区间，然后继续递归，直到走到 EI。

每层只访问一个节点，输出所有穿刺区间需要 O®，单词查询需要 O (r + logn) 的时间复杂度。

范围树

正交查询：给定平面点集，对任何矩形区域报告所有落在区域内的所有点。扩展至 n 维。

考虑 2 维问题，相当于 2 次 1 维查询。先筛选出 (x₁,x₂] 内的点，再筛选出 (y₁,y₂]，但是对时间有浪费。

回归一维问题：

基于叶子的 BBST，由有序的叶子节点搭建起来，内部节点存储路标信息，叶子节点存储实际数值。

在建树时保证了任何一个内部节点的路标数值 = 右子树所有叶子的最小值

描述了查询的切割过程，离开共同祖先之后，一旦在左藤蔓上向左走，说明左子树是被切割的部分需要发生递归继续切割下一层，而右子树是被包含在内的（建树保证）且不会被右侧切割，于是可以被完整打包。右藤蔓类似，向右走就打包左子树。

多层搜索树：也就是树套树

可以将原先的一维查询扩展到二维。对于 x 查询构建一棵 x- 树，对于 x- 树中每一个节点，都对应一棵子树 V。构造一棵对应的 yTree (V)，可以由 x 查询找到对应的 y- 树。于是还可以扩展到更高维度，MLST：多层搜索树。

经过 x 查询找到 O (logn) 棵子树，找到关联的 O (logn) 棵 y- 树，分别 y- 查询

总计耗时 $\sum^{O (logn)}_{i = 1}{r_i + O (logn)}=O (r + log^2n)$​

预处理建树阶段，从叶子出发逐层捉对合并，自底向上构造向 x- 树，也同步构造每个节点的 y- 树。每层的所有 y- 树构建时间之和是 O (n)，于是总记 O (nlogn)。不能共用一棵 y- 树！因为这样会导致构建起来的新树不是 BBST！

空间角度来看，每层的 y 树互不重叠，且覆盖所有 n 个点，高度 logn，于是空间 O (nlogn)

对于更高维度，可以在 O (nlog^d-1n) 构造 d 层 MLST，需要 O (nlog^d-1n) 空间，每次范围查询在 O (r + log^dn) 完成

分散级联：事实上对于 2 维正交查找，最后一个阶段的 y- 查询可以直接输出，于是用一个有序数组存储、二分查找即可。而这些查找本身 y 的范围是相同的。

于是在父子之间的 y- 列表中建立捷径引用，父亲的二分查找可以直接得到左右儿子的二分查找结果。

在构造树的时候，自底向上逐层合并 y- 列表，二路归并。任何点 P 在即将出列归入父亲的 y- 列表时左右儿子 y- 列表此时首元素就是 P 的捷径应该指向的点。

查找的时候只在 LCA 处对 y- 列表做二分查找。比如对左藤蔓，在逐渐下沉的时候不断更新捷径指针，这样在任何时刻都有当前节点做二分的结果。如果需要把右子树整个统计，由于有当前节点向右的捷径，可以在 O (1) 时间内拿到右子树 y- 列表的二分查找上下端。

引入了分散级联的 MLST 称作范围树。在 O (nlogn) 的时间内构造出一棵二层树，只需要 O (nlogn) 空间，每次二维范围查找可以在 O (r + logn) 时间内完成。