不相交整数区间的高效数据结构

Question

我有一组不相交的整数区间，想检查给定的整数是否位于其中一个区间。当然，这可以通过对数时间内的二进制搜索来实现。然而，绝大多数查询返回false，即任何时间间隔内只有很少的整数。为了加快应用程序的速度，我正在寻找一种概率的、恒定时间的算法（某种哈希函数），它可以告诉我给定的整数是绝对不是，还是可能在某个区间内。下面是预期算法的草图，其中使用存储在树中的间隔初始化magic\u data\u结构：

x = some_integer;
if(!magic_data_structure.find(x))
  return false; // definitely not in any interval
return tree.find(x); // binary search on tree

对文学有什么想法或提示吗？非常感谢您的帮助！

附言：有人知道对非重叠间隔的间隔树的改进吗？

Answer 1

这是一个幼稚的解决方案，但始终如此。

如果您不处理非常大量的数字，您可以使用哈希表，其中键是数字，值是指向它们所在集合的指针。但是当然，如果有很多数据，以这种方式索引它可能需要太长时间（和太多内存）。

看起来有各种不相交的集合数据结构和算法来存储/搜索它们，但我怀疑其中是否有常数时间。