Question

Is there a data structure that supports $$$n$$$ of the following operations in $$$O(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$$$ and a set, split the set into two sets: one with all elements less than $$$x$$$ and one with all elements greater than or equal to $$$x$$$.
4. For any integer $$$x$$$ and a set, add $$$x$$$ to all elements in the set. This operation is only allowed if all elements will remain in the range $$$[1,n]$$$.
5. Count the number of elements in a set.

Partial Solutions

If operation 2 required the ranges to be disjoint, any balanced BST that supports split and join in $$$O(\log{n})$$$ will work.

Without operation 3, join-based tree algorithms will work since they support 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})$$$ time total.)

Without operation 4, a version of 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})$$$. (Was this "well known" before?)

If we merge using split and join, this bound is tight. A set can be constructed by merging the set of even-index element and odd-index elements, which will take $$$O(n\log{n})$$$. Those two sequences could have been constructed the same way recursively. This will take $$$O(n\log^2{n})$$$ time for $$$O(n)$$$ operations.

However, I conjecture that if we use join-based tree algorithms, it will actually be $$$O(n\log{n})$$$ in the worst case. (For example, in the case above, merges take $$$O(n)$$$.)

Can anyone prove or disprove this conjecture for any join-based tree algorithm?

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

Thanks.