范围交叉算法优于O(n)？

Question

范围交叉是一个简单但非平凡的问题.

已经回答了两次:

• 查找数字范围交叉点
• 比较日期范围

第一个解决方案是O(n),第二个解决方案是数据库(当然小于O(n)).

我有同样的问题,但对于一个大的n,我不在数据库中.

这个问题似乎与存储2D点非常相似,可以快速检索矩形内的那些,但我看不到它是如何映射的.

那么你将数据结构存储在哪个数据结构中,以便搜索范围的成本低于O(n)？(使用可用于Java的库的额外功劳)

编辑:

我想获得所有相交范围的子集,这意味着搜索范围可以与多个范围相交.

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

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

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

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

Answer 1

标准方法是使用间隔树.

在计算机科学中,间隔树是用于保持间隔的树数据结构.具体而言,它允许人们有效地找到与任何给定间隔或点重叠的所有间隔.它通常用于窗口查询,例如,查找矩形视口内的计算机化地图上的所有道路,或查找三维场景内的所有可见元素.类似的数据结构是段树.

简单的解决方案是访问每个间隔并测试它是否与给定的点或间隔相交,这需要O(n)时间,其中n是集合中的间隔数.由于查询可以返回所有间隔,例如,如果查询是与集合中所有间隔相交的大间隔,则这是渐近最优的; 但是,我们可以通过考虑输出敏感算法来做得更好,其中运行时以m表示,即查询产生的间隔数.间隔树的查询时间为O(log n + m),初始创建时间为O(n log n),同时将内存消耗限制为O(n).在创建之后,间隔树可以是动态的,允许在O(log n)中有效插入和删除间隔.如果间隔的端点在小的整数范围内(例如,在[1,...的范围内,

Answer 2

编辑: 听起来这个解决方案或多或少是一个间隔树.可以在此处找到更完整的间隔树实现.

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):

1. 创建范围列表
2. 选择枢轴点(可能使用结束日期的排序列表.)??
3. 建立你的树.

搜索:

1. 使用二进制搜索查找> = TestRange.End的第一个数据透视表

2. 遍历树,直到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

Answer 3

非重叠范围:

准备O(n log n):

1. 制作范围的数组/向量.
2. 在范围的末尾对向量进行排序(通过按范围的开始排序来断开关系)

搜索:

1. 使用二进制搜索查找End值> = TestRange.Start的第一个范围

2. 迭代器从二进制搜索开始,直到找到Start> TestRange.End:

   2A.如果当前范围的范围在TestRange中,请将其添加到结果中.