Interval union-split-find

In computer science, an interval union-split-find data structure is a data structure that stores a partition of the integer interval $[1,n]$ into intervals. Equivalently, it stores a set of elements from $[1,n]$ ("splitters"), which define the endpoints of the intervals; for example, if n=10 and the set of endpoints is $\{1,4,8\}$ then the intervals are $[1,3],[4,7]$ and $[8,10]$. The data structure provides the following operations:

• split(x) adds x as a splitter, thus splitting the interval containing it (if x has not already been a splitter)
• union(x) for merging two intervals by removing the splitter x
• find(x) for finding which interval x belongs two (returning the interval's endpoint).

The problem is an instance of the dynamic predecessor problem, with a universe of size n.

Using Van Emde Boas trees, the data structure can be implemented with $O(\log \log n)$ time per operation, in $O(n)$ space. A matching lower bound has been proved by Mehlhorn, Näher and Alt under the assumption of a pointer algorithm. Under the assumptions of the cell-probe model, Beame and Fich proved that a data structure that uses word size $2^{(\log n{)}^{1-\Omega (1)}}$ must cost $\Omega (\log \log k/\log \log \log k)$ per operation, where k is the number of intervals.

The Union-Split-Find problem is important for a number of applications, e.g. dynamic fractional cascading and computing shortest paths.

The Interval Union-Find Problem

This is the subproblem that consists of supporting the find and union operations only. It can be solved by a disjoint-set data structure in $O(\alpha (n))$ amortized time per operation, or by a specialized RAM algorithm in O(1) amortized time.

The Interval Split-Find Problem

This is the subproblem that consists of supporting the find and split operations only. It has an O(1) amortized time solution on a RAM. It can also be solved by a pointer-based algorithm in $O(m\alpha (m,n))$ time for m operations.