UNION-COPY STRUCTURES AND DYNAMIC SEGMENT TREES

A new data structure-the union-copy structure-is introduced, which generalizes the well-known union-find structure. Besides the usual union and find operations, the new structure also supports a copy operation, that generates a duplicate of a given set. The structure can enumerate a given set, find all sets that contain a given element, insert and delete elements, etc. All these operations can be performed very efficiently. The structure can be tuned as to obtain different trade-offs in the efficiency of the different operations. As an application of the union-copy structure, we give a dynamic version of the segment tree. Contrary to the classical semi-dynamic segment trees, the dynamic segment tree is not restricted to a fixed universe, from which the endpoints of the segments must be chosen. The tree allows for insertions, splits, and concatenations in O(log n)-time each. Deletions can be performed in slightly more time.