What data structure would efficiently store integer ranges?

Problem Detail: 

I need to keep a collection on integers in the range 0 to 65535 so that I can quickly do the following:

• Insert a new integer
• Insert a range of contiguous integers
• Remove an integer
• Remove all integers below an integer
• Test if an integer is present

My data has the property that it often contains runs of integers in the collection. For example, the collection might at one point in time be:

{ 121, 122, 123, 124, 3201, 3202, 5897, 8912, 8913, 8914, 18823, 18824, 40891 } 

The simplest approach is just to use a balanced binary tree like the C++ std::set, however, using that, I am not leveraging the fact that I often have runs of numbers. Perhaps it would be better to store a collection of ranges? But that means a range needs to be able to be broken up if an integer in its middle is removed, or joined together if the space between two ranges in filled in.

Are there any existing data structures that would be well suited for this problem?

Asked By : WilliamKF

Answered By : D.W.

I suggest you use a binary search tree, augmented so that leaves can contain an interval (a run of consecutive integers). Maintain the invariant that the intervals do not overlap and are in order (following the search tree invariant). (This can be considered a special case of an interval tree or a segment tree, for the special case where the intervals do not overlap.)

This data structure you can support all of your operations in $O(\lg n)$ time, where $n$ is the number of intervals. Since we're guaranteed $n\le 65535$, I would expect this to be quite efficient. (In particular, yes, you can split an interval into two pieces or merge two adjacent intervals into a single interval in $O(\lg n)$ time.)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13874