范围交集是一个简单但并非微不足道的问题。
它已经回答了两次：
第一个解决方案是O（n），第二个解决方案是数据库（当然小于O（n）。
我有同样的问题，但对于一个大n，我不在数据库中。
这个问题似乎与Store 2D点非常相似，以便快速检索矩形内的那些点，但我不明白它是如何映射的。
那么，您将存储范围集在什么数据结构中，以便对范围进行搜索的成本低于O（n）？（使用可用于Java的库的额外学分）
编辑：
我想获取所有相交范围的子集，这意味着搜索范围可以相交多个范围。
在Java中需要小于O（n）的方法是：
public class RangeSet {
....
public Set<Range> intersects(Range range);
....
}
其中，Range 只是一个包含一对 int 开始和结束的类。
这不是一个不可能的问题，我已经有了解决方案，我只是想看看是否有更标准/更简单的方法。
标准方法是使用间隔树。
在计算机科学中，间隔树是用于保存间隔的树数据结构。具体来说，它允许人们有效地找到与任何给定间隔或点重叠的所有间隔。它通常用于窗口查询，例如，在矩形视口内查找计算机化地图上的所有道路，或查找三维场景中的所有可见元素。类似的数据结构是段树。
简单的解决方案是访问每个区间并测试它是否与给定的点或区间相交，这需要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间隔。
编辑：听起来这个解决方案或多或少是一个间隔树。可以在此处找到间隔树的更完整的实现。
class TreeNode
{
public:
long pivot;
List<Range> leaves; //Any ranges that intersect the pivot
TreeNode left; //Tree nodes that fall to the left of the pivot
TreeNode right; //Tree nodes that fall to the right of the pivot
};
Prep O（n log n）：
搜索：
遍历树，直到透视> TestRange.Start
2a.将叶子添加到结果中。
例：
范围：
树：
4
--------------+------------------
3 | 7
| 1-4 |
| 2-4 |
| 0-5 |
| 4-5 |
---------+------ --------+--------
2 | null 6 | null
-----+---- 2-3 ----+---- 3-7
null | null null | null
0-2 2-6
1-2
