c++ - 在线区间并集的长度

Question

我需要一个数据结构来存储一组间隔并允许计算它们的联合长度。

1假设在和之间有一组整数端的区间n。最初它是空的，可以添加或删除间隔。在每次操作之后，应该计算集合中所有区间的并集长度。

如何通过具有O(log n)时间复杂度的线段树来实现它，用于推送、删除和查找长度？应该在节点中存储什么？

Answer 1

Storing the minimum and the number of elements that have the minimum value in each node is sufficient here. Adding an interval is equivalent to adding 1 to a range and removing an interval is equivalent to adding -1 to a range. The length of the union is:
1. n if the minimum value is not zero for the root of the tree.
2. n - c, where c is the number of elements with the minimum value for the root of tree if the minimum is zero.
The minimum cannot be negative(any point is always covered by 0 or more intervals).