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](https://en.wikipedia.org/wiki/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](https://codeforces.me/blog/entry/56771?#comment-405367).↵
↵
Full Solution↵
==================↵
I was able to [prove](https://codeforces.me/blog/entry/66194?#comment-502207) 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.
==================↵
↵
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](https://en.wikipedia.org/wiki/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](https://codeforces.me/blog/entry/56771?#comment-405367).↵
↵
Full Solution↵
==================↵
I was able to [prove](https://codeforces.me/blog/entry/66194?#comment-502207) 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.
