What data structure can I use to store and retrieve ranges of discrete values?

Question

I have a JavaScript program in which I will be managing a lot of ranges of integers. In this context, a range is simply a start and an end value (or anything equivalent, like a start and a length value), with a reference to another object. The ranges can overlap, and can be identical (although the referenced object will be different).

The possible start and end values are between 0 and 4294967295 (2³² - 1 or 0xFFFFFFFF), although there are several big "holes" in the domain that no range will ever cover, even partially. Most ranges will be very small compared to the domain of possibilities: I expect that the overwhelming majority will have a length smaller than 2000.

My most important use case for this structure will be to look up all ranges that contain a given integer value. Most of the time, I expect the lookup to fail (there will be no range containing the given value).

Otherwise, I will obviously also need to add elements to it (often) and delete elements from it (seldom). Once in a while, too, I'll need to find all ranges that overlap a given range, rather than all ranges that contain a single value.

What kind of data structure can I use for that? A linear search in a list of ranges is impractical because the lookups fail most of the time; and I need to do lookups very, very often.

Answer 1

binary tree where the key is the start (low) value. Once you find a key you can look wide (higher and lower) fairly easily.