使用分段树查找重叠间隔的总长度？

Question

我们有一些区间,例如[1; 4] [7; 13] [9; 14]输入应返回3 + 6 + 1 = 10.当动态插入或删除间隔时,是否有任何方法可以使用分段树来查找这些间隔的总长度？

PS:我想过这样做而不使用分段树,但时间复杂度并不能满足我.

先感谢您

Answer 1

假设间隔存储在数组 [m,n] 中。另一个假设是数组已排序。

您需要做的就是找到较小的差异：

 int totalIntervales = 0;
 for(int index = 0; index < array.length ; index++)
 {
     int currentIntrval = array[index, 1] - array[index, 0];
     int differnceFromPrevious = array[index, 1] - array[index- 1, 1]
     totalIntervale += currentIntrval  > differnceFromPrevious ? differnceFromPrevious : currentIntrval;
 }
 return totalIntervale;

小心处理0位置即可。