计算几何中的正交范围查询（Orthogonal Range Search），旨在快速响应与坐标轴对齐的“长方形/立方体”范围的对象查找。
对象为点的查找
思路：范围树
一维查找
有序向量可以解决这个问题，但它不能扩展到高维。为此，我们使用建立平衡二叉树的预处理方法，叶子节点是对象本身，内部节点存储左子树包含的对象的最大值。若已经对象已经排好序，则预处理是 O(n) 的，否则是 O(n log n) 的。
查询 [a, b] 范围内的对象，只需在搜索树中查找 a, b，到达叶节点 u, v。假设从树根到 u 和树根到 v 的路径在 z 处之后分歧，那么列出范围内对象的方法为：从 u 到 z，报告所有“右边”的子树；从 z 到 v，报告所有“左边”的子树。
如果仅需要范围内对象的个数，那么查询是 O(log n) 的；如果要列出每个对象，则查询需要遍历每个“子树”，是 O(k + log n) 的。数据结构称范围树（range tree）
二维查找
我们需要查找 [x1, x2] x [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 范围树的空间复杂度，每个 y-range tree 的大小是 O(m) 的（m为子树大小），由于 x-range tree 的子树大小之和 Sigma_i m = 1*n + 2*(n/2) + … = n log n，所以整体的空间复杂度为 O(n log n) 的。
最终，考察构造 2D 范围树的时间复杂度。朴素的方法是 O(n) 时间建立 x-range tree，然后对每个子树独立建立 y-range tree，用时 Sigma_i O(m log m) = O( n (log n)^2 )。但是，如果自底向上构造每个子树的 y-range tree，就可以利用左右孩子的y-range tree，进行 O(m) 的归并代替 O(m log m) 的排序，所以时间复杂度降为 O(n log n)。
d 维查找
沿着以上思路，构造 d 维范围树，不难看出其查询时间为 O(k + (log n)^d)。不难由数学归纳法证明，构造它的时间复杂度为 O(n (log n)^{d-1}) 的。理由：每上升一个维度， Sigma_i m (log m)^{d-1} = n log n * (log n)^{d-1} = n (log n)^{d}。
另一种推导预处理复杂度的方法是主定理【附注1】。设对 n 个对象建立 k 维范围树的复杂度为 T_k(n)。由于范围树是自底向上构造的，考虑最后一步（构造出左右两个规模各为一半的范围树后，构造树根对应的低一维范围树）T_2(n) = 2*T_2(n/2) + O(n)，T_2(n) = O(n log n)。T_3(n) = 2*T_3(n/2) + T_2(n), T_3(n) = O(n (log n)^2)。以此类推。
使用分散层叠
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 范围树。倒数第二维（2d 范围树），让父节点和左右孩子节点的有序向量相链接（这是因为左右孩子节点的有序向量包含在父节点的有序向量中）。在查询最后两维 [x1, x2] x [y1, y2] 时，从树顶开始，一边依据 [x1, x2] 决定下降方向，一边在维护有序向量中 [y1, y2] 值区间对应的下标区间。整个查找过程是 O(k + log n) 的。
应用这个过程，d 维范围树的查找优化到了 O(k + (log n)^{d-1}) 的 (d>1)。
思路：k-d 树
范围树的空间占用高，预处理的时间空间开销大。k-d 树牺牲了查询复杂度，但结构更简单，实际性能也很好。
二维 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 的子问题。递归地拆分，设拆分规模为 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 树的搜索
搜索 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 中至多有 4Q(n) = O(n^{1/2}) 个子 cell 与长方形范围相交，因此搜索过程的复杂度为 O(k + n^{1/2})
高维 k-d 树
同理推导，搜索过程的复杂度为 O(k + n^{1-1/d})
对象为线段的查找
构造区间树的过程就像拿竹签子串串；构造线段树的过程就像让条带下落到树上，断开成若干段挂在树上。
区间树
问题：给定一维的 n 个区间，如何在 O(k + log n) 时间内列出包含某个点的所有线段（设有 k 条）？（称这个问题为 stabbing query）
思路：建立一颗”区间树 (Interval tree)“。列出所有区间端点，找出中位数（xm），作为根节点，存储所有包含该点的区间，这些区间按左端点和右端点顺序存储两次。剩下的区间要么在 xm 的左边，要么在 xm 的右边，分别为它们递归建立一颗区间树，作为根节点的左右孩子。
区间树的空间复杂度是 O(n) 的，不加证明地断言建立区间树用时 O(n log n) ，树高是 O(log n) 的。
查找方法：查询的点为 xq，若 xq==xm，直接输出根节点存储的所有区间即可；不妨设 xq < xm，那么1）遍历根节点存储的按左端点排序的区间，列出所有区间，直到左端点 > xq；2）递归地查询左孩子的区间树。
不难看出，查询的时间是 O(k + log n) 的。
线段树
问题：给定平面中不相交的N条线段，准备应对如下询问：给定一个新的竖直线段，返回所有与之相交的线段。
思路：考虑输入线段的x坐标投影，用所有端点的 x 坐标，将 x 轴划分为一系列区间。以这些区间为叶子节点建立一个平衡二叉树（称线段树 segment tree）。若线段 s 包含了节点 v（是线段），却不包含节点 v 的父节点，则把 s 存到 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。
思路：仿照计算几何的线段树，如果要更新的区间包含节点 v，却不包含 v 的父节点，则把该更新的信息记录在 v 上。由于这个标记不会立刻向 v 的左右孩子传递，称它为懒惰标记。在节点 v 上，维护该区间所有数的和。
代码：假设我们堆状建树，下标为 p 的左右孩子为 2*p, 2*p+1，则设懒惰标记数组为 lazy，区间和数组为 sum。由于懒惰标记的存在，sum 与真实的区间和之间有差距，相差祖先的累积懒惰标记乘以区间长度。
不变量是：
- 全局：真实区间和 = 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, …, （这里 ~ 借用了 git 中的用法）不变量变为：
- 全局：真实区间和 = (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，然后依据线段树的局部不变量计算。
附注
【附注1】主定理
假设输入大小为 n 的算法的运行时间满足 T(n) = a*T(n/b) + f(n)
情况1：f(n) = O(n^c), c<log_b(a)
则 T(n) = BigTheta(n^{log_b(a)})
情况2：f(n) = BigTheta( n^{log_b(a)} * (log(n))^k ), k \geq 0
则 T(n) = BigTheta( n^{log_b(a)} * (log(n))^{k+1} )
情况3：f(n) = BigOmega(n^c), c>log_b(a)
如果存在 k < 1, 满足任意足够大的 n，a*f(n/b) <= kf(n)，则 T(n) = BigTheta(f(n))
【附注2】quickselect 算法
从 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 应满足 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)。
Leave a Reply