algorithm - 查找包含给定数字的所有区间

Question

我有一个可能重叠的间隔列表。然后，我有一个值，问题是找到包含该值的所有区间，该值本身包含在内。我见过几种方法，包括范围树、KD树等。但是，我想知道是否有针对这个问题的特定优化解决方案，考虑到：

1. 间隔列表很长。（可能是 50K 或更多）。
2. 间隔可能重叠。
3. 一旦我们开始查询，间隔列表就不会改变。
4. 列表一旦形成，就会以不同的值被多次查询。

有人可以提出一些解决这个问题的方法。提前致谢。

Answer 1

这是一个定义明确的问题，使用区间树最有效地解决了这个问题（参见维基百科，这里和这里）以获得解释。

我不推荐使用哈希表，因为对于有很多重叠的配置，您最终可能会为每个条目存储 O(n) 个段，总共需要 O(n^2) 个存储空间。

Answer 2

如果您不介意昂贵的初始化时间，您可以使用您提到的任何技术来预先计算您在查询阶段可能遇到的所有相关值的间隔，限制为最小值和最大值。

用这些结果构造一个哈希表，您将能够在 O(1) 中找到给定值的所有区间。