查询某个范围内相交分段的个数
查询某个范围内相交分段的个数
提问于 2020-05-07 13:17:02
我有一个很大的数据集，其中包含(ai, bi)、where ai < bi和许多查询。每个查询询问具有给定范围(b, e)的相交线段的数量。查询的数量可能非常大。一个朴素的算法是在每个查询中搜索所有相交的片段，这显然需要O(N)时间。有没有更快的方法来做这件事？我可以想象，按照ai的升序对片段数据集进行排序可能会有所帮助，但我不知道如何处理另一个方向。
segments: [1, 3], [2, 6], [4, 7], [7, 8]
query 1: [2, 5] => output [1, 3] [2, 6], [4, 7]
...回答 1
Stack Overflow用户
发布于 2020-05-07 15:47:47
创建排序起点的列表B，如您所写的。
创建包含所有点的结构列表-包括起点和终点，以及相应的起点和终点字段SE = +1/-1。按点坐标对其进行排序。
生成Active = 0。遍历P，将SE添加到Counter，并创建包含点位置和A计数的新列表Active。
对于每个查询开始搜索(使用二进制搜索)在A中的较低位置，获取Active -此时打开的段的数量。
然后在B中搜索对应于查询开始和查询结束的索引，得到索引差异-查询间隔内开始的段数。
这些值的总和是number of intersected segments所需要的(根据问题陈述，您不需要片段本身)
每次查询的时间为O(log(N))
[1, 3], [2, 6], [4, 7], [7, 8] initial list
[1, 2, 4, 7] list B
(1,1),(2,1),(3,-1),(4,1),(6,-1),(7,-1),(7,1),(8,-1) list P
(1,1),(2,2),(3,1), (4,2),(6,1), (7,0), (7,1),(8,0) list A
^
q start 2 gives active = 2 (two active intervals)
searching 2 in B gives index 1, searching 5 gives index 2,
difference is 1
result = 2 + 1 = 3页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/61650382
复制相关文章
相似问题
腾讯云开发者
