Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

On the time complexity of merging BSTs

Revision en1, by dragonslayerintraining, 2019-06-27 02:32:34

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.

History

Revisions

Rev. Lang. By When Δ Comment
en3 dragonslayerintraining 2019-06-27 03:32:34 0 (published)
en2 dragonslayerintraining 2019-06-27 03:28:36 951 Tiny change: 'og{n})$?\n1. Creat' -> 'og{n})$?\n\n\n1. Creat'
en1 dragonslayerintraining 2019-06-27 02:32:34 1417 Initial revision (saved to drafts)