问范围合并长度

EN

现在，假设您有一个包含起始点和结束点的排序数组，该数组的约定是起点先于具有相同坐标的终结点。对于您的示例，数组将包含

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 )复杂性来插入/删除，而不是在数组中，您可以在一个平衡的二叉树中存储相同的元素(一对坐标和开始或结束标志)。然后，根据无序遍历执行扫描。

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

这并不完全是O(lg n)，但区间树或段树是否适合您的需要？您可以在变量中保留并集的长度，当插入或删除一个间隔时，您可以在O(lg n + m)时间中找到其他m间隔与它相交的内容，然后使用该信息在O(m)时间中更新length变量。

维护一个频率阵列。例句:如果你的范围是(0,2)和( 1，3)，你的频率阵列应该是1，2，2，1。同时保持频率阵列中非零元素的计数。

对于插入，增加对应于该范围的频率。更新计数从0增加到1(但不是从1增加到2等等)。

为了删除，减少频率。同样，更新计数。

对于查询，输出计数。

复杂性是范围的长度。