algorithm - 如何确定一个范围内有多少元素在另一个给定范围内？

Question

我需要一点帮助来弄清楚一些事情:

给定一系列无序数字(小于 15.000)- A - 我必须回答Q 查询(Q <= 100000) 形式为 i, j, x, y 翻译如下:

在 A 的 [i,j] 范围内有多少个数大于(或等于)x 但小于 y 并且序列中的所有数都小于 5000。

我的印象是这需要像 O(logN) 这样的东西，因为序列的长度很大，这让我想到了 BIT(二进制索引树——因为查询)但是 2D BIT 太大了，需要即使在更新方面也有很多时间可以运行。所以我在这里看到的唯一解决方案应该是 1D BIT 或线段树，但我不知道如何根据这些数据结构制定解决方案。我尝试保留有序数字集中的位置，但我不知道如何制作响应给定形式查询的 BIT。

此外，对于给定的限制，该算法应该适合500ms。 编辑 1: 500 毫秒用于所有预处理和回答查询的操作

EDIT 2: 其中 i, j 是序列 A 中第一个和最后一个元素的位置，用于查找大于 x 小于 y 的元素

编辑 3: 示例: 假设有 1、3、2、4、6、3 和查询 1、4、3、5 所以在位置 1 和 4(含)之间有 2 个元素(3 和 4)大于(或等于)3 和小于大于 5

提前致谢! P.S:抱歉英语不好!

Answer 1

通过制作一个由排序的子数组组成的 BIT 组织数组来实现二维范围计数。例如，在输入上

[1, 3, 2, 4, 6, 3]

神谕会是

[[1]
,[1, 3]
,[2]
,[1, 2, 3, 4]
,[6]
,[3, 6]
].

空间使用量为 O(N log N)(希望没问题)。如果您小心，构造需要 O(N log N) 时间，否则需要 O(N log^2 N) 时间(没有理由对您的应用程序如此)。

要回答序列索引和值最大值的查询(其中四个可用于回答输入查询)，对最大索引执行 BIT 读取过程，在数组中使用二进制搜索来计算元素的数量不超过最大值。查询时间为O(log^2 N)。