algorithm - 查找包含数字的范围的算法

Question

假设您有这样的“范围”类型（伪代码）：

Range {
    int lowerBound
    int upperBound
}

你有一个范围的集合，其中范围可能重叠：

var ranges = [Range{2, 5}, Range{8, 12}, Range{1, 3}, ...]

给定一个整数i ，检索包含i的每个范围（即 lowerBound < i < upperBound）的有效方法是什么？

我想出的可能的解决方案：

一种天真的 O(n) 方法当然是迭代范围并返回每个范围，其中 lowerBound < i < upperBound。但是我需要针对不同的i值多次运行该算法，并且有数百万个范围，所以这种幼稚的解决方案是不可接受的。

更有效的解决方案是按 lowerBound 的值按升序对范围进行排序。这样，算法只需要遍历范围，直到它到达 lowerBound > i 的第一个范围（因为如果 lowerBound > i，范围不可能包括i）。

如果我们在将所有i值输入算法之前对它们进行排序，则可以进一步改进（实际上，在我的实现中，i值已经按升序给出，因此我们不会因为不得不“排序”它们而损失任何性能） . 通过这样做，如果它们的 upperBound 小于给定的i值，我们将能够从集合中删除范围，从而减少对未来i值的比较。这种方法是迄今为止我提出的最有效的解决方案，但由于允许范围重叠，我正在努力实施它。因为范围可以重叠，并且考虑到我们按 lowerBound 对范围进行排序，所以找到 upperBound < i的范围的唯一方法将在 O(n) 中遍历它们。如何有效地完成此解决方案的实施？（或者是否有更有效的完全不同的解决方案？）

标签： algorithmperformancesortingrange

Answer 1

创建一个段树。它的叶子对应于您在范围内的不同边界值，它们代表到下一个边界的间隔。所以这些间隔不重叠。它的节点保存关于它们代表哪个（更大）间隔的信息——它下面的叶间隔的并集。对于每片叶子，您还确定（一次）在该间隔内哪些范围是“开放的”。

使用二分搜索，您可以找到代表具有您的搜索值的区间的叶子，因此您还可以从该叶子中获得适用的范围。

如果您以结束索引超出范围（不包括在内）的方式定义范围，则效果最佳。

对于您的示例[Range{2, 5}, Range{8, 12}, Range{1, 3}]，叶子将是：

[1, 2): [Range{1, 3}]
[2, 3): [Range{1, 3}, Range{2, 5}]
[3, 5): [Range{2, 5}]
[5, 8): []
[8, 12): [Range{8, 12}]