范围并集的长度

我需要在一维坐标系中查找范围并集的长度。我有很多范围[a_i，b_i]，我需要找到这些范围的联合长度。范围可以动态添加或删除，可以在任何状态下查询范围并集的长度。范围并集的长度

例如：是范围是：

[0-4] 
[3-6] 
[8-10]

输出应该8.

是否有此目的的任何合适的数据结构与复杂以下上限：

Insertion - O(log N) 
Deletion - O(log N) 
Query - O(log N)

没有，有没有这样的结构，将做到这一点，你必须自己编写 –

@EugenHalca你是什么意思，我当然会写我自己，我只是查询的名称。 –

什么会使输出8？对于这个联盟，我看到[0-6]，[8-10]。如果可能的值是0,1,2,3,4,5,6和8,9,10，则总数为10. –

一时间，假设你有一个排序的数组，同时包含起点和终点，与起点之前的终点与同一坐标的惯例。与您的示例中，阵列将包含

0:start, 3:start, 4:end, 6:end, 8:start, 10:end

（如果有在3结束的时间间隔，然后3:start将先3:end）

要执行的查询时，执行扫描从左至右，递增一个在“开始”计数器和在“结束”递减一个计数器。您记录为S计数器从0增加的位置，并记录为 E计数器变为零的位置。此时，您需要在总数中加上S和E之间的元素数。这也是一个重点，你可以用区间[S, E]替换前面的区间。

现在，如果需要O（log n）的用于插入/缺失的复杂性，而不是在阵列中，则存储元件相同的元件（对坐标和开始或结束标志）在平衡二叉树。然后根据inorder遍历执行扫描。

查询本身保持O（n）的复杂性。

2013-12-12 22:08:32 chill

您仍然可以使用数组并使用二进制搜索来插入/删除O（log n）。 – justhalf

而我的猜测是，查询的下界是Ω（n）。考虑覆盖其他区间范围的单个区间的情况。当你删除这个间隔时，我想你需要检查一切。但这只是一个想法。 =） – justhalf

我想我能得到的最好是O（n）查询。我尝试了一些其他的数据结构，它将范围存储为树的节点（树叶），插入和删除是O（log N），但在最坏的情况下查询是O（n）。 –

这不完全是O(lg n)，而是interval tree或segment tree是否符合您的需求？你可以保持联盟的长度在一个变量，并插入或取出的时间间隔时，您可以在O(lg n + m)时间什么其他米间隔交叉处找到，然后利用这些信息在O(m)及时更新长度是可变的。

2013-12-12 21:59:10

保持频率阵列。例如：如果你的范围是（0,2）和（1,3），你的频率数组应该是[1,2,2,1]。还要保持频率数组中非零元素的计数。

为了插入，增加对应于该范围内的频率。当你从0增加到1（但不是从1到2等）时更新计数。

对于删除，减少频率。同样更新计数。

用于查询，输出计数。

复杂性是范围的长度。

2013-12-13 06:12:06 ElKamina

回答