Length of union of ranges

Question

I need to find length of union of ranges in one dimension coordinate system. I have many ranges of form [a_i,b_i], and I need to find the length of union of these ranges. The ranges can be dynamically added or removed and can be queried at any state for length of union of ranges.

for example: is ranges are:

[0-4]
[3-6]
[8-10]

The output should be 8.

Is there any suitable data structure for the purpose with following upper bounds on complexity:

Insertion - O(log N)
Deletion - O(log N)
Query - O(log N)

Answer 1

For a moment, assume you have a sorted array, containing both start and end points, with the convention that a start point precedes an end point with the same coordinate. With your example, the array will contain

0:start, 3:start, 4:end, 6:end, 8:start, 10:end

(if there was an interval ending at 3, then 3:start will precede 3:end)

To do a query, perform a sweep from left to right, incrementing a counter on "start" and decrementing a counter on "end". You record as S the place where the counter increments from 0 and record as E the place where the counter becomes zero. At this point you add to the total count the number of elements between S and E. This is also a point, where you can just replace the preceding intervals with the interval [S, E].

Now, if you need O(log n) complexity for insertion/deletion, instead of in an array, you store the same elements (pairs of coordinate and start or end flag) in a balanced binary tree. The sweep is then performed according to the inorder traversal.

The query itself stays O(n) complexity.

Answer 2

It's not quite O(lg n), but would an interval tree or segment tree suit your needs? You can keep the length of union in a variable, and when inserting or removing an interval, you can find in O(lg n + m) time what other m intervals intersect it, and then use that information to update the length variable in O(m) time.