java - 比 O(n) 更好的范围相交算法？

Question

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

已经回答过两次了:

• Find number range intersection
• Comparing date ranges

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

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

这个问题似乎和 Store 2D points for quick retrieval of those inside a rectangle 很相似但我看不出它是如何映射的。

那么，您会将范围集存储在什么数据结构中，这样对范围的搜索成本低于 O(n)？ (使用可用于 Java 的库的额外功劳)

编辑:

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

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

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

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

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

Answer 1

标准方法是使用 interval tree .

In computer science, an interval tree is a tree data structure to hold intervals. Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point. It is often used for windowing queries, for instance, to find all roads on a computerized map inside a rectangular viewport, or to find all visible elements inside a three-dimensional scene. A similar data structure is the segment tree.

The trivial solution is to visit each interval and test whether it intersects the given point or interval, which requires O(n) time, where n is the number of intervals in the collection. Since a query may return all intervals, for example if the query is a large interval intersecting all intervals in the collection, this is asymptotically optimal; however, we can do better by considering output-sensitive algorithms, where the runtime is expressed in terms of m, the number of intervals produced by the query. Interval trees have a query time of O(log n + m) and an initial creation time of O(n log n), while limiting memory consumption to O(n). After creation, interval trees may be dynamic, allowing efficient insertion and deletion of an interval in O(log n). If the endpoints of intervals are within a small integer range (e.g., in the range [1,...,O(n)]), faster data structures exist[1] with preprocessing time O(n) and query time O(1+m) for reporting m intervals containing a given query point.