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

Let's assume that the algorithm you want exists. Then let's create a set of a million intervals, each being [1, 1], with random depths, and insert them into such interval tree. Then let's query the interval [1, 1]. It should return all the intervals in sorted order, with complexity O(M + log N), but N = 1, so we are sorting a set of M elements in linear time.

In other words, sorting elements by depth after you get them from the interval tree is as good in terms of complexity as it is theoretically possible.