Is there a data structure supporting $$$n$$$ of the following operations in $$$(n\log{n})$$$? 1. Create a set containing a single integer in the range $$$[1,n]$$$ 2. Create the union of two sets, destroying the original sets in the process. The original sets may have overlapping ranges. 3. For any integer $$$x$$$, split a set into all elements less than $$$x$$$ and all elements greater or equal to $$$x$$$ 4. For any integer $$$x$$$ such that all elements will remain in the range $$$[1,n]$$$, add $$$x$$$ to all elements in a set.

Partial Solutions

If operation 2 required the ranges to be disjoint, any balanced BST that supports split and join will work.

Without operation 3, join-base tree algorithms will work due to supporing union in $$$O(m\log{\frac{n}{m}+1})$$$

(Note that this is better than small to large, which takes $$$O(n\log^2{n})$$$.)

Without operation 4, segment trees will work.

Full Solution

I was able to prove that binary search trees will solve the problem in $$$O(n\log^2{n})$$$.

However, I conjecture that if we use join-based tree algorithms, it will actually be $$$O(n\log{n})$$$.

Can anyone prove or disprove this statement?

If anyone can prove it for splay trees instead, I would also be interested.

Thanks.