在线时间间隔的合并长度

Question

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

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

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

Answer 1

在这里存储每个节点中具有最小值的元素的最小值和数目就足够了。添加间隔等于将1添加到范围，而删除间隔则等于将-1添加到范围。工会的长度是：

1. 如果树根的最小值不是零，则为n。
2. n - c，其中，如果最小值为零，则c是树根的最小值的元素数。 最小值不能为负值(任何点总是由0或更多的间隔覆盖)。