范围交叉算法优于O（n）？
范围交叉是一个简单但非平凡的问题。
已经回答了两次：
- 查找数字范围交叉点
- 比较日期范围
第一个解决方案是O（n），第二个解决方案是数据库（当然小于O（n））。
我有同样的问题，但对于一个大的n，我不在数据库中。
这个问题似乎与存储2D点非常相似， 可以快速检索矩形内的那些，但我看不到它是如何映射的。
那么你将数据结构存储在哪个数据结构中，以便搜索范围的成本低于O（n）？ （使用可用于Java的库的额外功劳）
编辑：
我想获得所有相交范围的子集，这意味着搜索范围可以与多个范围相交。
在Java中需要小于O（n）的方法是：
public class RangeSet { .... public Set intersects(Range range); .... } 其中Range只是一个包含一对int start和end的类。
这不是一个不可能的问题，我已经有了解决方案，我只是想看看是否有更标准/更简单的方法
标准方法是使用区间树 。
在计算机科学中，区间树是用于保持间隔的树数据结构。 具体而言，它允许人们有效地找到与任何给定间隔或点重叠的所有间隔。 它通常用于窗口查询，例如，查找矩形视口内的计算机化地图上的所有道路，或查找三维场景内的所有可见元素。 类似的数据结构是段树。
简单的解决方案是访问每个间隔并测试它是否与给定的点或间隔相交，这需要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 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.End的第一个数据透视表
-
遍历树，直到pivot> TestRange.Start
2A。 将叶子添加到结果中。
例：
范围：
- 0 – 2
- 1 – 2
- 2 – 3
- 1 – 4
- 2 – 4
- 0 – 5
- 4 – 5
- 2 – 6
- 3 – 7
树：
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）：
- 制作范围的数组/向量。
- 在范围的末尾对向量进行排序（通过按范围的开头排序来断开关系）
搜索：
- 使用二进制搜索查找End值> = TestRange.Start的第一个范围
-
迭代器从二进制搜索开始，直到找到Start> TestRange.End：
2A。 如果当前范围的范围在TestRange中，请将其添加到结果中。
这取决于您的确切问题，在链接的问题中，不同的范围，没有共同的部分，以及搜索的范围可能跨越多个范围。 如果您的问题是相同的，那么它非常简单：取一个范围数组，按它们的最低值排序（因为它们不重叠，这也是按其上限值排序的顺序）。
现在只需对目标较低的值进行binsearch（如果不精确，则为较小值），对目标较高值进行一次binsearch（如果不精确，则为较大值）。 结果索引是覆盖的范围。 您必须检查索引本身的范围是在 – 或排除，但这只是2次检查。 总体复杂度O（log n）。
重叠范围：
准备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]); }
搜索：
- 使用二进制搜索查找End值> = TestRange.Start的第一个范围
-
迭代器从二进制搜索开始直到stop [i]> TestRange.End：
2A。 如果当前范围的范围在TestRange中，请将其添加到结果中。
如果范围重叠，并且想要检索重叠（或包含）给定目标范围的所有范围，则上述大多数解决方案似乎不起作用。
正如一些人所指出的，如果（最坏情况） 所有范围恰好与目标范围相交（例如，如果目标范围是{0..MAXINT}或类似），那么当然需要O（n）返回n范围。
但是不是有趣且典型/平均的情况，其中n个总范围中只有很小一部分与目标范围相交？ 调用与“m”相交的数字 – 在这种情况下，你可以想象能够做到与O（m）一样好。 如果n = 10 ^ 9且m = 10，则这是一个成败的区别。
考虑一个文本文档的简单情况，该文档具有为其“类型”标记的各种区域 – 可能您希望找到包含或交叉给定连续文本范围的所有标记单元（例如，段落）。 在HTML，XML或类似的中，它们只能是包含目标范围的至少一些字符的文本节点的祖先。 在每个节点中具有父指针的典型表示中，O（m） – 方式优于O（n），特别是因为m（对于短或同步目标范围）仅仅是树嵌套深度，其往往甚至低于ln（n）因为实际上大的XML文档变得越来越粗糙。
有趣的情况更难：如果您的“元素”不像XML那样形成树，但可以像MECS，CLIX，LMNL和其他一些系统那样重叠？ 您仍然希望找到与目标重叠的所有区域/“元素”，但它们不是那么容易组织的。
另一方面，你应该能够做得很好，因为许多应用程序中的标记范围通常很小 – 书中的单词，句子和段落比章节要多得多。 因此，即使可能有大量的范围在目标之前开始，而大量的范围在其之后结束，但交叉点的平均值非常小。
我认为这就是原始提问者所得到的，我担心我没有看到解决该问题的答案。 如果它不是原始问题的内容，那么我想把它作为一个新问题。
听起来你需要一个实现SortedSet接口的类。 TreeSet是随核心API一起提供的实现。
有一组保持按最低值排序的范围，一组按最高值排序。
然后，您可以使用内存集实现等效的数据库算法。
至于这是否实际上比O（n）更快，我不能说。
就像四叉树适用于一组2d点一样，一个简单的二叉树应该适用于这种情况。 用你的范围构建一棵树。
进一步解释：树中的每个节点包含两个整数，范围的开始和结束，以及两个子节点（如果它不是叶节点）。 要查找输入范围跨越的范围，请从树的顶部开始
- 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）
更多细节：二叉树的结构类似于四叉树的一维版本。 每个节点都有三个整数（抱歉我上面说过两个，但现在我意识到你需要三个），最低值表示低于此节点的最低值的最低值，最高值表示低于此值的最高值的最高值节点和枢轴。 左边的孩子将从这个节点的最低点到其枢轴。 正确的孩子将从此节点的枢轴跨越到此节点的最高点。 如果只有一个范围从“最低”到“最高”，你将没有一个支点，这将是一片叶子。 理想情况下，您需要为每个节点选择枢轴以保持树的平衡。
当我遇到这个问题时，我使用了一个排序的范围数组和二分搜索来寻找交叉点。 这是（我相信）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(loweroth.lower) { return 1; } if(upperoth.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[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); xafir || codepoints[idx].upperlas ? 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. } }