Question
Is there a data structure that supports $$$n$$$ of the following operations in $$$O(n\log{n})$$$?
- Create a set containing a single integer in the range $$$[1,n]$$$.
- Create the union of two sets, destroying the original sets in the process. The original sets may have overlapping ranges.
- 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$$$.
- 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]$$$.
- 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.