比 O(n) 更好的范围交集算法？

范围交集是一个简单但不平凡的问题。

已经回答过两次了：

• 查找数字范围交集 https://stackoverflow.com/questions/224878/find-number-range-intersection
• 比较日期范围 https://stackoverflow.com/questions/143552/comparing-date-ranges

第一个解决方案是 O(n)，第二个解决方案是针对数据库的（当然小于 O(n)）。

我有同样的问题，但是对于一个大的 n 并且我不在数据库内。

这个问题似乎非常类似于存储 2D 点以便快速检索矩形内的点 https://stackoverflow.com/questions/303243/store-2d-points-for-quick-retrieval-of-those-inside-a-rectangle但我不明白它是如何映射的。

那么，您将在什么数据结构中存储范围集合，以便对范围进行搜索的成本低于 O(n)？ （使用可用于 Java 的库的额外学分）

EDIT:

我想获得所有相交范围的子集，这意味着搜索范围可以与多个范围相交。

Java中需要小于O(n)的方法是：

public class RangeSet {
    ....
    public Set<Range> intersects(Range range);
    ....
}

其中 Range 只是一个包含一对 int start 和 end 的类。

这不是一个不可能的问题，我已经有了解决方案，我只是想看看是否有更标准/更简单的方法来做到这一点

标准方法是使用区间树 http://en.wikipedia.org/wiki/Interval_tree#With_an_Interval.

在计算机科学中，区间树是一种保存区间的树数据结构。具体来说，它允许人们有效地找到与任何给定间隔或点重叠的所有间隔。它通常用于窗口查询，例如，在矩形视口内的计算机化地图上查找所有道路，或者查找三维场景内的所有可见元素。类似的数据结构是线段树。

简单的解决方案是访问每个区间并测试它是否与给定点或区间相交，这需要 O(n) 时间，其中 n 是集合中区间的数量。由于查询可能返回所有间隔，例如，如果查询是与集合中的所有间隔相交的大间隔，则这是渐近最优的；但是，我们可以通过考虑输出敏感算法来做得更好，其中运行时间以 m（查询产生的间隔数）表示。区间树的查询时间为 O(log n + m)，初始创建时间为 O(n log n)，同时将内存消耗限制为 O(n)。创建后，区间树可以是动态的，从而允许在 O(log n) 内高效地插入和删除区间。如果间隔的端点在一个小整数范围内（例如，在 [1,...,O(n)] 范围内），则存在更快的数据结构[1]，预处理时间为 O(n) ，查询时间为 O( 1+m)用于报告包含给定查询点的m个间隔。