Take a look at: Richard Bonichon and Pascal, Cuoq, A Mergeable Interval Map
link, 2010. I've spent a bit of time trying to find the original journal where this was published, but this link is the most stable one.
I cannot say that I followed all of the proofs and logic in that paper, but I understood enough to realize that it wasn't what I was looking for, but I think it is meant to solve your range query.
The solution data structure should, for instance, be able to answer
queries such as finding all bindings that intersect a given interval. Being able to do this is necessary for lookups, but also at the time of adding a new binding, in order to maintain the invariant that the intervals in the map are disjoint.
The basic idea is to enforce a "covering" ordering logic on the nodes of a tree:
In Patricia trees, there is a static hi- erarchy for deciding which node goes above the other, and this static hierarchy ensures trees are balanced or almost balanced without any re-balancing operations. In the case of our data structure, we similarly define a static ordering on intervals that tells which node must be placed above the others. Intuitively, the interval containing the multiple of the largest power of two is put at the top. Like the ordering in Patricia trees, this ordering has the bounded chain length property...
I also recommend understanding Okasaki's Fast Mergeable Integer Maps first.