5
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

Please read about Interval Tree.

$\endgroup$
  • 2
    $\begingroup$ At present, this is only a comment. Do interval trees solve the problem in a straightforward way? If so, say it. Otherwise, explain what needs to be done. $\endgroup$ – Yuval Filmus Jan 29 at 5:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.