范围联合的长度

Question

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

例如:范围是:

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

输出应为8.

是否有任何合适的数据结构用于以下复杂性的上限:

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

Answer 1

暂时假设您有一个已排序的数组，其中包含起点和终点，并且约定起点位于具有相同坐标的终点之前。在你的例子中，数组将包含

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) 复杂度的插入/删除，而不是在数组中，您可以将相同的元素（坐标对和开始或结束标志）存储在平衡二叉树中。然后按照中序遍历进行扫描。

查询本身的复杂度保持为 O(n)。