2024-10-12
计算几何中的正交范围查询（Orthogonal Range Search），旨在快速响应与坐标轴对齐的“长方形/立方体”范围的对象查找。
有序向量可以解决这个问题，但它不能扩展到高维。为此，我们使用建立平衡二叉树的预处理方法，叶子节点是对象本身，内部节点存储左子树包含的对象的最大值。若已经对象已经排好序，则预处理是 O(n) 的，否则是 O(n log n) 的。
查询 [a, b] 范围内的对象，设实际上一共有 k 个这样的对象，后文分析查询时间复杂度时中出现的符号 k 也沿用这一含义。只需在搜索树中查找 a, b，到达叶节点 u, v。假设从树根到 u 和树根到 v 的路径在 z 处之后分歧，那么列出范围内对象的方法为：从 u 到 z，报告所有“右边”的子树；从 z 到 v，报告所有“左边”的子树。
如果仅需要求出范围内对象的个数 k ，那么查询是 O(log n) 的；如果要列出每个对象，则查询需要遍历每个“子树”，是 O(k + log n) 的。数据结构称范围树（range tree）
我们需要查找 $[x1, x2] * [y1, y2]$ 长方形范围内的点。推广一维的思路，首先忽略 y 坐标，建立一个 x 坐标的范围树（x-range tree）。然后，在每个内部节点，对其子树包含的点建立一个 y 坐标的范围树（y-range tree）。这样就得到了一个 2D 范围树。
查找的方法为，首先搜索 x-range tree，得到 O(log n) 个子树；然后对于每个子树搜索 y-range tree。因此总时间复杂度为 $O(k + (\log n)^2)$。
考察 2D 范围树的空间复杂度，在 x-range tree 中深度为 h 的每个 y-range tree 的子树大小是 $m=O(n/2^h)$ 的。因此，x-range tree 的子树大小之和可以通过按深度求和计算出来 $\Sigma_{h=0}^{\log n} 2^h (n/2^h) = 1*n + 2*(n/2) + 4*(n/4) + ... = n \log(n)$，所以整体的空间复杂度为 O(n log n) 的。
考察构造 2D 范围树的时间复杂度。朴素的方法是 O(n) 时间建立 x-range tree，然后对每个子树独立建立 y-range tree，用时 $\Sigma_{h=0}^{\log n} n * O(\log(n/2^h)) = n * \Sigma_{h=0}^{\log n} O(\log n - h) = O( n (\log n)^2 )$。但是，如果自底向上构造每个子树的 y-range tree，就可以利用左右孩子的 y-range tree，进行 O(m) 的归并代替 O(m log m) 的排序，所以时间复杂度降为 O(n log n)。
沿着以上思路，构造 d 维范围树，不难看出其查询时间为 $O(k + (\log n)^d)$。不难由数学归纳法证明，构造它的时间复杂度为 $O(n (\log n)^{d-1})$ 的。理由：每上升一个维度， $\Sigma_{h=0}^{\log(n)} n (\log (n/2^h))^{d-1} = O(n \log n * (\log n)^{d-1}) = O(n (\log n)^{d}) $。
另一种推导预处理复杂度的方法是主定理【附注1】。设对 n 个对象建立 d 维范围树的复杂度为 $T_d(n)$。由于范围树是自底向上构造的，考虑最后一步：构造出左右两个规模各为一半的范围树后，构造树根对应的低一维范围树。
$$ T_2(n) = 2*T_2(n/2) + O(n) \implies T_2(n) = O(n \log n) $$ $$ T_3(n) = 2*T_3(n/2) + T_2(n) \implies T_3(n) = O(n (\log n)^2) $$
以此类推，
$$ T_d(n) = 2*T_d(n/2) + T_{d-1}(n) = 2*T_d(n/2) + O(n (\log n)^{d-2}) \implies T_d(n) = O(n (\log n)^{d-1}) $$
Fractional Cascading（一般译为分散层叠，后面简称为 FC）将相关的数据结构链接到一起，从而从一个结构快速定位到另一个结构。使用分散层叠。
FC 最简单的例子是，给定两个有序向量 A 和 B，B 的元素都包含在 A 中，要查找 [x1, x2] 范围内有哪些 A 的元素和 B 的元素。通过建立从 A 中元素到 B 中元素的链接，可以先对 A 做二分查找，而后通过链接列出 B 中元素，免去对 B 做二分查找。
A: 11 13 14 15 17 19 23 37 42 45
| | | | |
B: 11 14 15 23 37
应用在范围树中，我们在最后一维用有序向量代替 1d 范围树。在倒数第二维，让父节点的有序向量和左右孩子节点的有序向量相链接（这是因为左右孩子节点的有序向量包含在父节点的有序向量中）。在查询最后两维 [x1, x2] x [y1, y2] 时，从树顶开始，一边依据 [x1, x2] 决定下降方向，一边在维护有序向量中 [y1, y2] 值区间对应的下标区间。这样做，整个查找过程是 O(k + log n) 的。
应用这个过程，不难看出，d>1 维范围树的查找优化到了 $ O(k + (\log n)^{d-1}) $。
范围树的空间占用高，预处理的时间空间开销大。k-d 树牺牲了查询复杂度，但结构更简单，实际性能也很好。
轮流依据 x，y 坐标二分点集，每次选取坐标值的中位数。不断二分，直到类别中只剩下 O(1) 个数据点。这样得到的树必定是平衡的，即高度为 O(log n)。在内部节点，存储包围盒坐标，称这个包围盒为 cell。
构建的方法如下：
首先把点集按照 x 坐标排序、y 坐标排序，得到两个有序向量，在两个有序向量之间添加链接，用时 O(n log n)。
按 x 坐标中位数将 x 有序向量分为两半，然后依据 y 有序向量到 x 有序向量的链接，将 y 有序向量扫描一遍，拆成两半，花费 O(n) 时间。此时，问题别拆分为两个规模为 n/2 的子问题。递归地拆分（轮流依据 x,y 坐标），设拆分规模为 n 的子问题用时 T(n)，则 T(n) = 2T(n/2) + O(n)，由主定理，T(n) = O(n log n)。（由于这里向量是有序的，所以选取中位数循下标访问即可；通用的选取中位数方法见【附注2】）
因此，建立二维 k-d 树的时间复杂度为 O(n log n)；空间复杂度为 O(n)。
搜索 k-d 树的方法比较显然：若包围盒包含于范围，则汇报包围盒中全部对象；若包围盒部分包含于范围，则递归地搜索左右孩子。
为了推导如上过程的复杂度，考虑包含 n 个元素的 cell 中，与任意线段相交的子 cell 的个数，设为 Q(n)。下降两层后，得到 4 个子 cell，注意到线段只能与这四个子 cell 中的两个相交。因此，Q(n) = 2Q(n/4) + O(1), 依据主定理，$Q(n) = O(n^{1/2})$。因此，包含 n 个元素的 cell 中至多有 $4* Q(n) = O(n^{1/2})$ 个子 cell 与长方形范围相交，因此搜索过程的复杂度为 $O(k + n^{1/2})$。
与二维情况的推导同理。
构建过程的第一步，需要 $O(nd\log n)。$构建过程的第二步，轮流二分，$T(n) = 2T(n/2) + O(nd)$，由主定理，$T(n) = O(nd \log n)$。因此，构建过程的时间复杂度是$O(nd\log n)$。
输入数据的空间复杂度是 O(nk)，存储第一步的索引需要 O(nk) 的空间，而由于节点要存储包围盒，最终整棵树也需要 O(nk) 的空间。
搜索过程中，$Q(n) = 2^{d-1}Q(n/2^d) + O(1)$，依据主定理，$Q(n) = O(n^{1-1/d})$ ，因此复杂度为 $O(k + n^{1-1/d})$。
| 数据结构 | 构建时间复杂度 | 空间复杂度 | 查询时间复杂度 |
|---|---|---|---|
| range tree with FC | $O(n (\log n)^{d-1})$ | $O(n (\log n)^{d-1})$ | $ O(k + (\log n)^{d-1}) $ |
| kd tree | $O(nd\log n)$ | $O(nd)$ | $O(k + n^{1-1/d})$ |
下面介绍两种为查找线段设计的数据结构：区间树（Interval Tree）和线段树（Segment Tree）。直观地看，构造区间树的过程就像拿竹签子串串；构造线段树的过程就像让一个水平的条带竖直下落到树上，断开成若干段挂在树的不同高度上。
问题：给定一维的 n 个区间，如何在 O(k + log n) 时间内列出包含某个点的所有线段？（称这个问题为 stabbing query）
思路：建立一颗区间树 (Interval tree)。列出所有区间端点，找出中位数（xm），作为根节点，存储所有包含该点的区间，这些区间按左端点和右端点顺序存储两次。剩下的区间要么在 xm 的左边，要么在 xm 的右边，分别为它们递归建立一颗区间树，作为根节点的左右孩子。
区间树的空间复杂度是 O(n) 的，不加证明地，断言建立区间树用时 O(n log n) ，树高是 O(log n) 的。
查找方法：设查询点的坐标为 xq，若 xq=xm，直接输出根节点存储的所有区间即可；否则，不妨设 xq < xm，然后：1）遍历根节点存储的按左端点排序的区间，列出所有区间，直到左端点 > xq；2）递归地查询左孩子的区间树。xq > xm 的情况同理。
不难看出，查询的时间是 O(k + log n) 的。
问题：给定平面中不相交的N条线段，准备应对如下询问：给定一个新的竖直线段，返回所有与之相交的线段。
思路：考虑输入线段的x坐标投影，用所有端点的 x 坐标，将 x 轴划分为一系列区间。以这些区间为叶子节点建立一个平衡二叉树（称线段树 segment tree）。若线段 s 包含了节点 v（是线段），却不包含节点 v 的父节点，则把 s 存到 v 的节点列表中。由于线段是不相交的，所以该列表可以"从上到下"（选取区间 v 中任意一个 x 坐标，求出线段对应的 y 坐标）排序。
查询方法：使用竖直线段的 x 坐标查询平衡二叉树。每深入到一个节点，在该节点存储的列表中二分搜索找到符合 y 范围的线段汇报。
复杂度：平衡二叉树高度 O(log n)；每个线段被存储在 O(log n) 个节点；预处理时间空间 O(n log n)；查询时间O( k + log(n)^2 )
计算几何中的"线段树"允许在 O(log n) 时间查询给定点包含在哪些区间内。它的变种，编程竞赛/测试中的线段树允许使用 O(log n) 时间询问和变更一个区间。
问题：已知一个长度为 n 的数列，进行如下两种操作：1) 将某个（下标）区间中的每个数加上 k，2) 求出某个区间内所有数的和。有办法在 O(log n) 内完成每个操作吗？题目来自 Luogu P3372 【模板】线段树 1。
思路：建立计算几何中的线段树，每个内部节点维护 sum 和 lazy 两个变量。如果要更新的区间包含节点 v，却不包含 v 的父节点，则把该更新的信息记录在 v 上（具体而言用 lazy 变量）。由于这个标记不会立刻向 v 的左右孩子传递，称它为懒惰标记。在节点 v 上，维护该区间所有数的和。
代码：假设我们堆状建树，下标为 p 的左右孩子为 2*p, 2*p+1，则设懒惰标记数组为 lazy，区间和数组为 sum。由于懒惰标记的存在，sum 与真实的区间和之间有差距，相差祖先的累积懒惰标记乘以区间长度。
不变量包括：
一个全局关系：节点 p 区间内数字的和 = sum[p] + 回溯到根一路上懒惰标记的和 * 区间长度
一个局部关系：sum[p] = sum[2*p] + sum[2*p+1] + lazy[p] * p的区间长度
从根开始递归访问，如果区间和节点区间没有交集则直接返回，区间包含节点区间则添加懒惰标记并返回，区间和节点区间有交集则更新 sum 并递归访问左右孩子。
void awardlazy(segment* tree, int i, int amount) {
tree[i].lazy += amount;
tree[i].sum += amount * (tree[i].r - tree[i].l + 1);
}
void rangeadd(segment* tree, int i, int lo, int hi, int amount) {
if (lo > hi || hi < tree[i].l || lo > tree[i].r) return;
if (lo > tree[i].l && hi < tree[i].r) tree[i].sum += (hi - lo + 1) * amount;
else if (lo > tree[i].l) tree[i].sum += (tree[i].r - lo + 1) * amount;
else if (hi < tree[i].r) tree[i].sum += (hi - tree[i].l + 1) * amount;
else { // target interval contains node i
awardlazy(tree, i, amount);
return;
}
rangeadd(tree, 2*i, lo, hi, amount);
rangeadd(tree, 2*i+1, lo, hi, amount);
}
从根开始递归访问，如果区间和节点区间没有交集则直接返回 0，区间包含节点区间则直接返回 sum[p]（我们保证发生这种情形时，根到 p 的路径上所有懒惰标记都已清除），区间和节点区间有交集则把 lazy[p] “下放” 到它的左右孩子（左右孩子的 lazy 和 sum 都要更新）并返回
ll lookup(segment* tree, int i, int lo, int hi) {
if (lo > hi || hi < tree[i].l || lo > tree[i].r) return 0;
if (lo <= tree[i].l && hi >= tree[i].r) {
return tree[i].sum;
}
// need to recurse, propagate lazy mark
awardlazy(tree, 2*i, tree[i].lazy);
awardlazy(tree, 2*i+1, tree[i].lazy);
tree[i].lazy = 0;
return lookup(tree, 2*i, lo, hi) + lookup(tree, 2*i+1, lo, hi);
}
现在需要支持第三种操作：将某个区间中的每个数乘以 k。题目来自 Luogu P3373 【模板】线段树 2。
为此，我们为添加一个新懒惰标记，标记应该乘以多少。至此，有两个懒惰标记：add 表示“该加多少”，mult 表示“该乘多少”。
假设沿 p 回溯到根的路径依次经过 p~1, p~2, ..., （p~k 代表从 p 回溯 k 层）不变量变为：
全局：节点 p 区间内数字的和 = (sum[p] * mul[p~1] + len(p) * add[p~1]) * mul[p~2] + len(p) * add[p~2] ...
局部：sum[p] = (sum[2*p] + sum[2*p+1]) * mul[p]+ len(p) * add[p]
注意，计算的次序是“先乘后加”的。
// if has child, must propagate any existing lazy marks before adding new ones
void try_push_lazy(segment* tree, int i) {
if (tree[i].l != tree[i].r) {
tree[2*i].sum = (tree[2*i].sum * tree[i].lazy_mult + tree[i].lazy_add * (tree[2*i].r - tree[2*i].l + 1)) % MOD;
tree[2*i+1].sum = (tree[2*i+1].sum * tree[i].lazy_mult + tree[i].lazy_add * (tree[2*i+1].r - tree[2*i+1].l + 1)) % MOD;
tree[2*i].lazy_mult = (tree[2*i].lazy_mult * tree[i].lazy_mult) % MOD;
tree[2*i+1].lazy_mult = (tree[2*i+1].lazy_mult * tree[i].lazy_mult) % MOD;
tree[2*i].lazy_add = (tree[2*i].lazy_add * tree[i].lazy_mult + tree[i].lazy_add) % MOD;
tree[2*i+1].lazy_add = (tree[2*i+1].lazy_add * tree[i].lazy_mult + tree[i].lazy_add) % MOD;
// reset
tree[i].lazy_add = 0;
tree[i].lazy_mult = 1;
}
}
注意，一个节点可能同时有 add 和 mult 两种懒惰标记，需要依据“先乘后加”的运算规则下放，以保证不变量成立。
ll rangemult(segment* tree, int i, int lo, int hi, int mult) {
// assert that the path from root to i does not contain lazy add or mult
if (lo > hi || hi < tree[i].l || lo > tree[i].r) return tree[i].sum;
try_push_lazy(tree, i);
if (lo <= tree[i].l && hi >= tree[i].r) {
awardlazymult(tree, i, mult);
return tree[i].sum;
}
tree[i].sum = (rangemult(tree, 2*i, lo, hi, mult) + rangemult(tree, 2*i+1, lo, hi, mult)) % MOD;
return tree[i].sum;
}
该递归调用保证当前节点到树根的路径上没有懒惰标记。为了维护这个承诺，如果递归调用必须事先下放懒惰标记。
区间变更后的 sum 是通过让左右孩子返回自己的 sum 来计算的。
假设输入大小为 n 的算法的运行时间满足 T(n) = a*T(n/b) + f(n)
情况1：$f(n) = O(n^c), c<log_b(a)$,
则 $T(n) = \Theta(n^{log_b(a)})$
情况2：$f(n) = \Theta( n^{log_b(a)} * (log(n))^k ), k \geq 0 $
则 $T(n) = \Theta( n^{log_b(a)} * (log(n))^{k+1} )$
情况3：$f(n) = \Omega(n^c), c>log_b(a)$
如果存在 k < 1, 满足任意足够大的 n，$a*f(n/b) \leq kf(n)$，则 $T(n) = \Theta(f(n))$
从 n 个元素的无序列表中选取出第 k 大的元素，时间复杂度是多少？朴素的办法是排序 O(n log n)，而时间复杂度的下限是 O(n)，因为在访问所有元素之前不可能断言某个元素第 k 大。
quickselect 是一个平均用时 O(n) 的算法。它的思想和 quicksort 很像，选取一个支点 pivot，交换数组中的元素使得支点左边的元素不超过支点，支点右边的元素不小于支点：
# input pivot position, output new position of pivot after swap
def partition(A, lo, hi, pivot): # A[lo, hi]
pivotvalue = A[pivot]
A[hi], A[pivot] = A[pivot], A[hi] # swap pivot to right end
while lo < hi:
# fill gap at A[hi]
while lo < hi and A[lo] <= pivotvalue:
lo += 1
A[hi] = A[lo]
# fill gap at A[lo]
while lo < hi and A[hi] >= pivotvalue:
hi -= 1
A[lo] = A[hi]
A[lo] = pivotvalue
return lo
求第 k 小的元素，可以通过让 A[k-1] 成为支点解决。不断试探性地选取支点（策略较重要），交换数组元素，考察支点的新位置：如果恰好等于 k-1，则问题解决；如果小于 k-1，则我们可以只考虑右半边的数组；如果大于 k-1，则我们可以只考虑左半边的数组。
def kth_small(A, k):
k = k-1 # make A[k-1] a pivot
lo, hi = 0, len(A)-1
while lo < hi:
pos = partition(A, lo, hi, lo)
if pos <= k:
lo = pos+1
if pos >= k:
hi = pos-1
return A[k]
由上面的算法可见，在求出第 k 小元素的同时，quickselect 算法也保证了第 k 小元素出现在 A[k-1] 的位置，且 A[0..k-1) 不超过 A[k-1]，A(k-1..n) 不小于 A[k-1]，无序向量被分为了两部分。
设对 n 个元素求第 k 小，用时期望为 T(n)。试探性选择支点并交换数组元素，得知支点的下标变为 j, 从而将其转换为子问题的过程表明，$T(n) \leq (n-1) + (1/n) * \Sigma_{j=0}^{n-1} T(\max(j, n-j-1)) \leq (n-1) + (2/n) * \Sigma_{j=n/2}^{n-1} T(j) $。
不妨假设 $T(n) \leq c*n$，代入上述递推式，化简得到 $ c \leq (n-1)/n + (c/4) * (2n-2-n)/n * (2n-2+n)/n \leq 1 + c*3/4 $，取 c=4 即可。因此，quickselect 的平均用时为 O(n)。