Data structure for fast look up of ranges, but that allows insertion

Question

At work I'm looking for a data structure that supports the following operations:

$$insert(X, A, B)$$ $$delete(X)$$ $$glb(C)$$

$insert$ adds the range $[A, B)$ into the data structure with value $X$ associated with it AND shifts all ranges after (exclusive) $A$ by $B - A$.

$delete$ removes the range associated with $X$. Call that range $[A, B)$ then every range after (inclusive) $B$ is shifted back by $B - A$

The combination of $insert$ and $delete$ are meant to maintain the invariant that ranges never overlap. In order to actually maintain this however the user must never insert a range that has a lower bound contained in an existing range. So for instance if $[3, 7)$ had already been inserted then it would be invalid to insert $[4, 9)$ but it would be perfectly valid to insert $[1, 5)$ or $[1, 10)$

$glb(C)$ looks up the pair $(X, [A, B))$ such that $A$ is the greatest start of an interval less than or equal to $C$. Note that this does not mean that $C \in [A, B)$ as it could be that $C \gt B$

I'm hoping that I can do this in $\mathcal{O}(lg(n))$ or at least $\mathcal{O}(lg^2(n))$

Also it's highly advantageous if the data structure is a relatively simple data structure. Other practical things that might be of note $A$, $B$, and $C$ range over integers and $X$ can be hashed, ordered, and compared for equality. It's acceptable to have two data structures that we maintain a relationship between (for instancing maintaining a hash table that maps each $X$ to the node in the more complicated data structure that keeps track of the ranges).

So far the best thing I've been able to find is to maintain a finger tree and a hash table. The finger tree's keys are then the length of the interval. To insert like you would normally in a finger tree but you also store a mapping of $X$ to the node in the finger tree in a hash table. To delete you find the node of the value in the hash table then walk up the spine (so this finger tree needs back pointers) to perform the required delete on that child of the tree as normal. To find the $glb$ you perform the standard finger tree lookup. That should be logarithmic for all operations but I would rather have something simpler badly enough that I'd accept a polylogrithmic running time as a trade off.

Is there something simpler than this?

Answer 1

You can achieve $O(\log n)$ time for all operations using a self-balancing binary tree. Augment the tree so that you can store a value $\delta$ in each internal node; the meaning is that we add $\delta$ to the key of all descendants of that node. So the actual key value at a particular node is the key stored at that node, plus the sum of all $\delta$'s along the path to the root.

This makes it easy to shift over all intervals after $A$, by adding $\delta$ to $O(\log n)$ nodes chosen so that their descendants cover all the keys after $A$. It's also easy to adjust the lookup procedure to look up a value (the glb operation) and to find where to insert/delete a range.