arrays - 某个数字在特定范围内出现的次数？

Question

给定一个大的未排序数组，我需要找出给定数字在特定范围内的出现次数。（可以有很多查询）

例如，如果 arr []={ 6,7,8,3,4,1,2,4,6,7,8,9}and left_range=3and right_range=7and number=4，则输出将为 2。（考虑到索引为 0 的数组）

arr[i] 可以在 1 到 100000 的范围内。数组最多可以有 100000 个数字。

你能指导我在这里应该使用哪种数据结构或算法吗？

PS：允许对数组进行预处理。

Answer 1

这是一个不需要段树的解决方案。

预处理：

1. 对于每个 number arr[i]，将 i 推入索引为 的 2D 向量（或 ArrayList）arr[i]。

回答问题：

对于任何查询，对 vector[num] 进行二分搜索，以找到该向量中小于或等于右范围的 num 的最大索引的索引，我们称其为 R。然后找到大于或等于的最小索引左范围，我们称之为 L。打印 R - L + 1

运行时：每个项目在 O(1) 中进行预处理，总共花费 O(N) 时间。每个查询答案：O(lg(N))

空间：假设向量或 ArrayList 相当线性