DSA - 问题集第七章

清澈的大学生和有趣的数据结构，谁会赢？明天考两门估计复习不完了。

如何建树：全局预处理，按左边界升序和右边界降序排出两个区间序列。对每个节点找到所有端点中的 mid。从头到尾扫描 L 序列，完全在 mid 左侧的区间（也就是右端点在 mid 左）放 Lleft 序列，完全在 mid 右侧放 Lright 序列，经过 mid 的留在 L 序列中。对 R 序列同理完成。Lleft 和 Rleft 下发给左子树，同理下发右子树。完成建树。

不存在更强的建树算法：可以线性归约到排序，如果有更强的建树，那么考虑每个节点的 L 序列构成的中序遍历，相当于在 nlogn 之内完成排序，这是矛盾的。

如果允许存在相同端点没有常数上限；如果不允许存在相同端点，则考虑在 mid 左侧的所有端点集合（左或右）Eleft 和相应的 Eright。完全在 mid 左侧的区间贡献 2 个给 Eleft，完全右侧的贡献 2 个给 Eright，横跨的贡献 1 个给 Eleft1 个给 Eright。而因为 mid 是中位点所以 Eleft 和 Eright 数量相等 = n，2Sleft + Smid = n=2Sright + Smid，左右区间数量相等，也就是数量之差恰好 = 0。

b）这次二分递归之前的 R (v)，s 都没有覆盖中间的分裂点，也就不会完全覆盖。

a）在前面都是单侧递归；在其后右子树 s 一定紧贴 R (v) 的左边界，因为就是从这个地方被分开的，所以要么不覆盖左侧区间要么完全覆盖左侧区间；左子树情况同理，都是线性的。

LCA 到左边界的路径上左转就拿走右子树所有节点；右边界路径上右转拿走左子树所有节点。子树不超过 O (logn)：藤蔓上每一步最多贡献一个子树，高度 logn

在从底部向上搭建 x- 树的时候用归并合并两个 y- 树，形成更大的 y 树。范围树的元素是必须有重复的，每个内部节点都是叶子的副本。每次把坐标排开两两合并，维护子树最小节点，两个子树合并就是让父亲成为右子树的最小节点，同时父亲的子树最小节点是左子树的最小节点。关联的 y- 树当有序列表就行。

每一层构建的 y 树恰好不重不漏 n 个点每一层 O (n)，于是 O (nlogn)，空间同理。

十字交叉

不剩多少时间了，留待后人补充吧。