I need a data structure that stores a set of intervals and allows to calculate the length of their union.
Suppose that one has a set of intervals on the line with integer ends between 1 and n. Initially it is empty, and one can add or remove intervals to it. After each operation one should calculate the length of the union of all intervals in the set.
How can one implement it via the segment tree with O(log n) time complexity for pushing, removing and finding the length? What should one store in the nodes?
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).