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

Question

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

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

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

Answer 1

这里存储最小值和每个节点中具有最小值的元素的数量就足够了。添加一个区间相当于将一个区间加 1，移除一个区间相当于将一个区间加 -1。并集的长度为:
1. n 如果树的根的最小值不为零。
2. n - c，其中c是树的根节点中具有最小值的元素个数，如果最小值为零。< br/>最小值不能为负(任何点总是被 0 个或多个间隔覆盖)。