c - 算法——范围查询

Question

我正在尝试解决以下问题:

给定一个包含n 个元素的数组A，我们必须回答m 个类型为i,j,X 。对于每个查询，我们必须输出 i,j 范围内大于 X 的数字。

例如:

如果数组是:

3 4 1 7

查询是 1 4 3 即我们必须输出 1 到 4 范围内大于 3 的数字。

输出:2

因为三个数都大于3 (4, 7)

约束:

1 < n < 10^5
1 < A[i] < 10^9

我的方法:

我尝试使用 sqrt(n) 段的段树来接近它。它给出了 O(sqrt(n)) 的时间复杂度。

有没有其他方法可以用更小的复杂度来解决？

Answer 1

您要查找的数据结构是二维的 range tree .然而，以下方法具有 O(sqrt(n) log n) 操作时间，可能更容易实现。 (我将把对 O(sqrt(n log n)) 的改进作为练习。)

将奶牛分成 sqrt(n) 个连续的 sqrt(n) 奶牛 block 。对于每个 block ，按正常和额外的排序顺序存储符号。当处理 M 查询时，进行必要的更改和求助(时间 O(sqrt(n) log n))。处理 C 查询时，在未排序的数组中对部分重叠的 block (时间 O(sqrt(n)))使用蛮力，在排序的数组中对完全包含的 block 使用二分查找(时间 O(sqrt(n) log n)).

这是 O(log^2 n) 查询时间版本。保持segment tree排序的多重集，其中每个排序的多重集包含该段中奶牛的符号。处理 M 查询时，从包含该奶牛的段的所有多重集中删除该奶牛的旧标志。以类似的方式重新插入奶牛的新标志。处理 C 查询时，将查询区间划分为 O(log n) 段，并检查范围内每个已排序多重集中的元素数。支持后一种操作的最佳方法可能是二叉搜索树，其中每个节点都存储其左子树中的节点数。我没有首先建议的原因是 (i) 它需要更多的实现工作 (ii) 对于 n = 100000，运行时间函数的差异是 sqrt(n)/log(n)**(3/2) ~ 8，这很可能会被两种方法的相对缓存友好性和后者的额外复杂性所吞没。