算法 - 范围查询

Question

我试图解决以下问题:

给定的阵列甲的Ñ元素,我们必须回答米类型的查询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

您正在寻找的数据结构是2D 范围树.然而,具有O(sqrt(n)log n)操作时间的以下方法可能更容易实现.(我将把改进留给O(sqrt(n log n))作为练习.)

将奶牛分成sqrt(n)个连续的sqrt(n)奶牛块.对于每个块,通常以排序的顺序存储标志.处理M查询时,进行必要的更改并求助(时间O(sqrt(n)log n)).处理C查询时,在未排序的数组中对部分重叠的块使用强力(时间O(sqrt(n))),在完全包含的块的有序数组中使用二进制搜索(时间O(sqrt(n)) N)).

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