范围相交是一个简单但不平凡的问题。
它已经回答了两次：
第一个解决方案是 O(n)，第二个解决方案是用于数据库（当然小于 O(n)）。
我有同样的问题，但是对于一个大的 n 并且我不在数据库中。
这个问题似乎与存储 2D 点以快速检索矩形内的点非常相似，但我看不出它是如何映射的。
那么，您会将范围集存储在什么数据结构中，以便对范围的搜索成本低于 O(n)？（使用可用于 Java 的库的额外功劳）
编辑：
我想获得所有相交范围的子集，这意味着搜索范围可以与多个范围相交。
Java中需要小于O(n)的方法是：
public class RangeSet {
....
public Set<Range> intersects(Range range);
....
}
其中 Range 只是一个包含一对 int 开始和结束的类。
这不是一个不可能的问题，我已经有了解决方案，我只是想看看是否有更标准/更简单的方法
标准方法是使用区间树。
在计算机科学中，区间树是保存区间的树数据结构。具体来说，它允许人们有效地找到与任何给定区间或点重叠的所有区间。它通常用于窗口查询，例如，在矩形视口内查找计算机地图上的所有道路，或查找 3D 场景内的所有可见元素。类似的数据结构是段树。
简单的解决方案是访问每个区间并测试它是否与给定的点或区间相交，这需要 O(n) 时间，其中 n 是集合中的区间数。由于查询可能返回所有区间，例如，如果查询是与集合中所有区间相交的大区间，则这是渐近最优的；然而，我们可以通过考虑输出敏感算法做得更好，其中运行时间用 m 表示，m 是查询产生的间隔数。区间树的查询时间为 O(log n + m)，初始创建时间为 O(n log n)，同时将内存消耗限制为 O(n)。创建后，区间树可能是动态的，允许在 O(log n) 中有效地插入和删除一个区间。如果区间的端点在一个小的整数范围内（例如，在范围 [1,...,
编辑： 听起来这个解决方案或多或少是一个区间树。可以在此处找到更完整的区间树实现。
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
};
准备 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
非重叠范围：
准备 O(n log n):
搜索：
迭代器从二分搜索开始，直到找到 Start > TestRange.End：
2a. 如果当前范围在 TestRange 范围内，则将其添加到您的结果中。
重叠范围：
准备 O(n log n):
制作第二个整数向量。这表示您可以停止搜索的点。
int stop[size];
stop[size-1] = Ranges[size - 1].start;
for (int i = size - 2; i >= 0; i--)
{
stop[i] = min(Ranges[i].start, stop[i+1]);
}
搜索：
迭代器从二分查找开始，直到 stop[i] > TestRange.End：
2a. 如果当前范围在 TestRange 范围内，则将其添加到您的结果中。
这取决于您的确切问题，在链接的问题中，不同的范围，没有共同部分，并且搜索的范围可能跨越多个范围。如果你的问题是一样的，那真的很简单：取一个范围数组，按它们的最低值排序（因为它们不重叠，这也与按它们的最高值排序的顺序相同）。
现在只需对您的目标下限值（如果不准确则更小）和目标上限值（如果不准确则更大）进行 binsearch。结果索引是涵盖的范围。您必须检查索引本身的范围是否包含在内或排除在外，但这只是 2 次检查。总体复杂度 O(log n)。
如果范围重叠，并且想要检索与给定目标范围重叠（或包含）的所有范围，则上述大多数解决方案似乎都不起作用。
正如一些人指出的那样，如果（最坏情况）所有范围都恰好与目标范围相交（例如，如果目标范围是 {0..MAXINT} 或类似的）那么当然需要 O(n) 才能返回n 个范围。
但是，这不是有趣且典型/平均的情况吗，其中 n 个总范围中只有很小的百分比与目标范围相交？将与“m”相交的数字称为“m”——在这种情况下，可以想象你可以做得和 O(m) 一样好。如果 n=10^9 和 m=10，那就是成败的区别。
考虑一个文本文档的简单情况，该文档具有针对其“类型”标记的多个区域——也许您希望找到包含或与给定的连续文本范围（例如，段落）相交的所有标记单元。在 HTML、XML 或类似内容中，它们只能是包含目标范围内至少一些字符的文本节点的祖先。在每个节点中具有父指针的典型表示中，这是 O(m)——比 O(n) 好得多，特别是因为 m（对于短或同步目标范围）仅仅是树嵌套深度，它往往甚至低于ln(n) 因为大型 XML 文档在实践中变得更加复杂而不是更深。
有趣的情况更难：如果您的“元素”不像在 XML 中那样形成树，而是像在 MECS、CLIX、LMNL 和其他一些系统中那样重叠，该怎么办？您仍然希望找到与您的目标重叠的所有区域/“元素”，但它们并不那么容易组织。
另一方面，您应该能够做得很好，因为在许多应用程序中标记的范围通常都很小——一本书中的单词、句子和段落远多于章节。因此，即使可能有大量范围在目标之前开始，而在目标之后结束的范围也很大，但平均而言，交叉点将非常小。
我认为这就是最初的提问者所要解决的问题，恐怕我没有看到解决该问题的答案。如果这不是最初的问题，那么我想将其作为一个新问题提出。
就像四叉树适用于一组二维点一样，简单的二叉树也适用于这种情况。用你的范围构建一棵树。
进一步解释：树中的每个节点都包含两个整数，范围的开始和结束，如果它不是叶节点，则包含两个子节点。要查找输入范围跨越的范围，然后从树的顶部开始
- if the node range intersects the input range:
- if it's a leaf node, then add the range to your result list
- if it's not a leaf node, then traverse down to the child nodes and repeat this process.
它应该是 O(logN)
更多细节：二叉树的结构类似于四叉树的一维版本。每个节点将有三个整数（对不起，我在上面说了两个，但现在我意识到你需要三个），最低的代表低于此节点的最低范围的最小值，最高的代表低于此的最高范围的最大值节点和枢轴。左孩子将从这个节点的最低点跨越到它的枢轴。右子节点将从该节点的枢轴跨越到该节点的最高节点。如果只有一个范围从“最低”到“最高”，那么您将没有枢轴，这将是一片叶子。理想情况下，您会为每个节点选择枢轴以保持树的平衡。
听起来您需要一个实现 SortedSet 接口的类。TreeSet 是核心 API 附带的实现。
一组包含按最小值排序的范围，一组按最大值排序。
然后，您可以使用内存集实现等效的数据库算法。
至于这是否真的比 O(n) 快，我不能说。
当我遇到这个问题时，我使用了一个排序的范围数组和二进制搜索来寻找交叉点。这是（我相信）O(log n) 性能，处理重叠范围需要一点开销。
我认为，您的问题的答案可以从下面的代码中得出，但没有插入。我展示了整个代码以避免因不同的上下文而造成混淆——我需要将一系列 Unicode 代码点插入到代码点范围列表中。
- 编辑 -
调整下面的代码以确定多个范围的交叉点涉及从插入点开始的简单前向搜索，直到找到不再相交的范围。
-- 结束编辑 --
Range 类包含：
final int lower; // lower end of range
final int upper; // upper end of range
public int compareTo(Object obj) {
if(obj==null) { return -1; }
Range oth=(Range)obj;
if(lower<oth.lower) { return -1; }
if(lower>oth.lower) { return 1; }
if(upper<oth.upper) { return -1; }
if(upper>oth.upper) { return 1; }
return 0;
}
范围插入：
public Builder addRange(int fir, int las) {
if(fir!=-1) { fir&=0x001FFFFF; }
if(las!=-1) { las&=0x001FFFFF; }
if(codepoints==null || codepoints.length==0) {
codepoints=new Range[]{new Range(fir,las)};
}
else {
int idx=Range.findChar(codepoints,fir);
int ins=(idx<0 ? -(idx+1) : idx);
if(idx<0) {
if (ins>0 && fir==(codepoints[ins-1].upper+1)) { idx=(ins-1); } // new range adjoins the following range (can't overlap or idx would be >=0)
else if(ins<codepoints.length && las>=(codepoints[ins ].lower-1)) { idx=ins; } // new range overlaps or adjoins the following range
}
if(idx<0) {
codepoints=(Range[])Util.arrayInsert(codepoints,ins,new Range(fir,las));
}
else {
boolean rmv=false;
for(int xa=(idx+1); xa<codepoints.length && codepoints[xa].lower<=las; xa++) {
if(las<codepoints[xa].upper) { las=codepoints[xa].upper; }
codepoints[xa]=null;
rmv=true;
}
if(codepoints[idx].lower>fir || codepoints[idx].upper<las) {
codepoints[idx]=new Range((codepoints[idx].lower < fir ? codepoints[idx].lower : fir),(codepoints[idx].upper>las ? codepoints[idx].upper : las));
}
if(rmv) { codepoints=Range.removeNulls(codepoints); }
}
}
return this;
}
二进制搜索：
static int findChar(Range[] arr, int val) {
if(arr.length==1) {
if (val< arr[0].lower) { return -1; } // value too low
else if(val<=arr[0].upper) { return 0; } // value found
else { return -2; } // value too high
}
else {
int lowidx=0; // low index
int hghidx=(arr.length-1); // high index
int mididx; // middle index
Range midval; // middle value
while(lowidx<=hghidx) {
mididx=((lowidx+hghidx)>>>1);
midval=arr[mididx];
if (val< midval.lower) { hghidx=(mididx-1); } // value too low
else if(val<=midval.upper) { return mididx; } // value found
else { lowidx=(mididx+1); } // value too high
}
return -(lowidx+1); // value not found.
}
}