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 ${\displaystyle [1,n]}$ into intervals. Equivalently, it stores a set of elements from ${\displaystyle [1,n]}$ ("splitters"), which define the endpoints of the intervals; for example, if n=10 and the set of endpoints is ${\displaystyle \{1,4,8\}}$ then the intervals are ${\displaystyle [1,3],[4,7]}$ and ${\displaystyle [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 ${\displaystyle O(\log \log n)}$ time per operation, in ${\displaystyle O(n)}$ space. A matching lower bound has been proved by Mehlhorn, Näher and Alt^[1] 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 ${\displaystyle 2^{(\log n)^{1-\Omega (1)}}}$ must cost ${\displaystyle \Omega (\log \log k/\log \log \log k)}$ per operation, where k is the number of intervals.^[2]

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

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 ${\displaystyle O(\alpha (n))}$ amortized time per operation, or by a specialized RAM algorithm in O(1) amortized time.^[5]

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.^[5] It can also be solved by a pointer-based algorithm in ${\displaystyle O(m\alpha (m,n))}$ time for m operations.^[6]