In computer science, an interval union-split-find data structure is a data structure that stores a partition of the integer interval into intervals. Equivalently, it stores a set of elements from ("splitters"), which define the endpoints of the intervals; for example, if n=10 and the set of endpoints is then the intervals are and . 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 to (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 time per operation, in 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 must cost 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 amortized time per operation, or by a specialized RAM algorithm in O(1) amortized time.Harold N. Gabow, Robert Endre Tarjan, "A linear-time algorithm for a special case of disjoint set union," Journal of Computer and System Sciences, Volume 30, Issue 2, 1985, pp. 209–221, ISSN 0022-0000, https://doi.org/10.1016/0022-0000(85)90014-5
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 time for m operations.
References