整数流范围查询算法

Question

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

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

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

Answer 1

如果您维护了到目前为止从流中读取的整数的有序列表，则可以通过查找 a(使用二进制搜索)并从该点开始迭代直到您通过 b，这样查询所花费的时间将与结果的实际大小成正比，而不管范围填充得多么稀疏。