algorithm - 整数流范围查询的算法

Question

我的程序得到了一个正整数流。我必须在收到它们时存储它们，并且能够回答介于两者之间的范围查询。

我想到的一个简单的解决方案是将整数存储在哈希表中，其中键是整数的字符表示（键必须是我的哈希表中的字符串）。然后，每当范围查询 [a, b] 出现时，我可以简单地从 a 循环到 b，检查键是否存在，如果存在则检索值。但是，我不确定这是否是一个好方法。

这个问题还有哪些其他替代解决方案？

Answer 1

如果您维护了到目前为止读取的流中的整数的有序列表，则可以通过查找a（使用二进制搜索）并从该点迭代直到您通过来完成范围查询b，这样查询所花费的时间将成比例到结果的实际大小，无论填充的范围有多稀疏。