第一个解决方案是O（n），第二个解决方案是用于数据库（当然小于O（n））。
我有同样的问题，但是对于一个大n，我不在数据库内。
这个问题似乎与“ 存储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）时间，其中n是集合中间隔的数量。由于查询可能返回所有间隔，例如，如果查询是与集合中所有间隔相交的较大间隔，则这是渐近最优的；但是，通过考虑对输出敏感的算法，我们可以做得更好，在这种算法中，运行时间用m（查询产生的间隔数）表示。间隔树的查询时间为O（log n + m），初始创建时间为O（n log n），同时将内存消耗限制为O（n）。创建后，间隔树可能是动态的，从而允许在O（log n）中高效插入和删除间隔。如果间隔的端点在较小的整数范围内（例如，在[1，…，
