# Dynamic length of union of segments (1d Klee’s measure problem)

Finding the length of union of segments (1-dimensional Klee’s measure problem) is a well-known algorithmic problem. Given a set of $$n$$ intervals on the real line, the task is to find the length of their union. There is a simple $$O(n \log n)$$ solution involving sorting endpoints of all intervals and then iterating over them while keeping track of some counters.

Now let’s look at a dynamic variant of this problem: we are receiving $$n$$ segments one after another and the task is to find the length of the current union of segments after each new segment arrives. It seems like a natural generalization, however, I cannot find much information about this version of the problem. I wonder if it is still possible to solve this problem in $$O(n \log n)$$ time in an offline setting, i.e. when we are given all segments beforehand and can preprocess them in some way before giving an answer for each segment.

I feel like a modification of a segment tree might be useful here. In every node we need to keep track of both the total sum of lengths of segments (or their parts) corresponding to this node and the length of their union. However, I cannot figure out how to implement this modification without performance of one update degrading to linear time in some cases. Maybe using a segment tree is not the right approach and a better way exists.