algorithm - 范围并集的长度

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 之前)

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

现在，如果您需要 O(log n) 的插入/删除复杂度，而不是在数组中，您可以将相同的元素(成对的坐标和开始或结束标志)存储在平衡二叉树中。然后按照中序遍历进行扫描。

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