What data structure would efficiently store integer ranges?

Question

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?

Answer 1

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.)

Answer 2

First of all, your question is very poorly worded, if for no other reason because "quickly" doesn't mean much. You'll need to provide some metric of what "quick" means.

Beyond that, when trying to come up with a design for a problem you need to first understand the problem very well and ask a lot of additional questions. Relevant questions in this case would seem to be (in no particular order):

• Must all these operations be equally quick, or are some more important than others?
• Are there other considerations?
• Is memory a concern at all?
• Is the ability to perform insertions, removals and lookups from multiple threads a concern?
• Is the workload mostly focused on inserting? Removing? Looking up?

Secondly, if your problem domain really is $[0, 65535]$ then this discussion seems just silly. Is a smart, fancy algorithm really necessary? Especially when a simple array is an excellent option, covering the single integer operations in constant time, the range operations in linear time and costs linear space?

For a little bit more work, you could save on space if that's a concern, at the expense of speed by storing the data as bits in 8192 integers. Although conceptually the single integer operations would still be constant time and ranged integer operations would still be linear time, they would be slower.

So, if this is really your problem, I'd say use an array and move on to other, more important things with the code.

If this isn't really your problem and there are other considerations you haven't relayed (e.g. perhaps the domain isn't really $[0, 65535]$ and you were trying to simplify the problem you were asking about) then you'll need to ask your question again, this time telling us the actual problem.

Answer 3

You might consider an Integer data structure such as a Van Emde Boas tree. An Integer data structure works on a fixed universe $\mathcal{U}=\{0,\ldots,u-1\}$. Some of the operations you have mentioned can be implemented very efficiently. In particular, inserting, deleting and requesting a single element runs in $O(\log \log u)$. The other operations (bulk insert/delete) might be more costly, however, using bittricks on the Van Emde Boas tree you should be able to get a speed-up by a factor of about the the word size of your system.

Depending on the structure of your data there might be many clever alternatives how to store your data.