I am trying to create a data structure for handling the subsets of the real line of the form $[x,y)$. That is, suppose $X \subseteq \mathbb{R}$ and the data structure supports two types of operations: $add(X, [x,y))$ and $remove(X,[x,y))$. Each of these two queries return the number of disjoint semi-intervals in $X$. For instance,
> add(X, [2, 10))
> 1
> add(X, [3, 9))
> 1
> add(X, [-1, 1))
> 2
> remove(X, [2, 10))
> 1
I suspect that this can be realised with binary search tree, however I could not properly invent the behaviour. I still suspect this can be done in such a way that each query works in $O(\log n)$ time, where $n$ is the total number of queries. Can you please suggest anything?
