Sorted intervals query

Question

I'm in search for a data structure which efficiently operates over closed intervals with the following properties:

• dynamically add or remove an interval

• set, and anytime change, a number ("depth") for each interval. no two depths are ever the same

• find all intervals that overlap with any given interval, sorted by "depth"

The closest structure I found is Interval tree but it lists the found intervals in arbitrary order with respect to their depths. I could collect all the "unsorted" intervals as reported and sort them afterwards but I was hopping it was possible to avoid to sort the result for every query.

Please, does anyone know of such data structure or have any suggestion how (if at all possible) to enhance the Interval tree to support such sorting?

Example:

1. add [1,2] to the empty structure and set its depth to 1

2. add [10,100], depth = 2

3. add [5,55], depth = 3

4. query for [5,50] reports [10,100] and [5,55]

5. set depth of [10,100] to 3, and of [5,55] to 2

6. query for [5,50] reports [5,55] and [10,100]

Edit

I'm more interested in fast adds/removes and queries, than in updating of depths. A depth can take as much as O(n), if that helps speed-up the other operations.

Answer 1

Using an interval tree and sorting results is a great solution. It will have quite good running time. You can add, remove, or find an interval in $O(\log n)$ time and change the depth of an interval in $O(1)$ time once you've found it. Also, you can process an intersection query (report all intervals that overlap a given interval) in $O(\log n + m \log m)$ time, where $n$ is the total number of intervals and $m$ is the number of results.

Can you do better? It seems clear that you can't do very much better. Obviously, no comparison-based data structure can beat $\Omega(\log n + m)$ running time for intersection queries, so this trivial lower bound shows you are at most $\log m$ times slower than optimal.

Also, we can prove that no comparison-based data structure can beat $\Omega(\log n + m \log m)$ time for an intersection query in general, if you can change the depth of an interval in $O(1)$ time. Consider the case $n=m$, and where all intervals overlap and should be returned. If you could answer the intersection query faster than $O(m \log m)$ time, you could sort $m$ numbers faster than $O(m \log m)$ time, which we know is impossible for comparison-based algorithms. (Well, more precisely, if you have $t$ arrays of length $m$, and if you knew how to answer intersection queries in $O(\log n + m)$ time and change depths in $O(1)$ time, you could sort all $t$ of those arrays in $O(m \log m + t (m + \log m)) = O(m (t+ \log m))$ time using your data structure by adding $m$ copies of the same interval, changing all their depths based on the first array, doing an intersection query, then changing all of their depths based on the second array, and so on. However $O(m(t+\log m))$ running time is provably impossible for this task: the standard lower bound on comparison-based sorting shows that this takes $\Omega(t m \log m)$ time, and when $t$ is large enough, this is a contradiction -- e.g., when $t=m$, this would give a way to sort $m$ arrays of length $m$ in $O(m^2)$ time, when we know it actually takes $\Omega(m^2 \log m)$ time.)

So, if you want to hope for a data structure that allows intersection queries to run strictly faster than $\Theta(\log n + m \log m)$, you either need to allow changing the depth of an interval to take longer than $O(1)$ time, or you need to consider non-comparison-based data structures.

If you knew that your depths were all small integers, you could speed up this algorithm by using a faster sorting algorithm optimized for that case (e.g., counting sort). However in practice existing sorting algorithms are already very fast so it's not clear whether this would make a big difference in practice.

So this algorithm already seems quite good, and it seems unlikely that we can beat it using comparison-based data structures. If you want to do better, you'll have to specify a model of computation (e.g., the RAM model), but it's unclear that algorithms with a better asymptotic running time will lead to something that is faster in practice.