Multi tool use

To get the total length of overlapped intervals using Segment tree with lazy propogation

So here's the problem: given a set of intervals [a,b) where a,b is integers,0<=a < b=10^5, what's the length of all the interval(overlapped parts will only be counted once)? if we want to support two operations: add(a,b), and remove(a,b) ([a,b) exist in the set in the case of remove), which add and remove interval [a,b) to and from the set then return the new total length, can you do them in O(logn), where n is 10^5? .eg: if we have interval [1,3),[2,4), then the total length is 3 in this case.

My approach to it is using Segment tree, nodes of which is

class Segnode:
def __init__(self,start,end):
self.start,self.end = start,end
self.left,self.right = None,None
self.layer,self.cover = 0,0
self.lazy = 0


where layer record how many intervals cover this node (eg: if we have a set of [0,3),[1,3),[1,2), then the Segnode(1,3) will have layer 2, because only [0,3) and [1,3) totally cover it); cover record the length of the part of this node that covered(eg: Segnode(1,3) in last example will have cover 2).

Segnode(1,3)

Segnode(1,3)

But the thing is I couldn't come up with a correct,LAZY way to update the tree (if we don't use lazy propagation then the problem is trivial, but time complexity could reach O(n) where n could be 10^5 per operation). Can someone help me with this part? is there a correct, lazy approach to this?

Thank you very much.

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.