Hello there
so I'm trying to solve this problem
It's about finding the gcd of a set of numbers where i insert and delete numbers from the set
I already solved it with a segment tree, and after learning about treas i tried solving it with a treap but it TLEd on testcase 18
now my question is: aren't treaps on average Log(n)? if so ... shouldn't it pass where segment tree did with complexity of stable Log(n)?
here's my treap code for reference for maybe the error is in my implementation
Treaps are solwer than segment trees. If you are able sving a problem using a segment tree there is no point in writing a treap. So in fact treaps are slower, because the operations are with complexity c*depth where c is the number of times you call merge/split. Another thing you should consider is that the depth of the treap is bigger than the depth of the segment tree, because it's not a perfectly balanced binary tree. So the complexity of the segment tree is lesser than the treap's complexity. But this is just a comparison between the two data structures's complexities. The pros of the treap are that you are able of doing much more operations using just merge and split (like Cyclic shift, reverse and etc).
So in short:
if you are able using a segment tree — use segment tree.
Else use (implicit) treap/avl.
roger that ... another question ... AVL trees ... they are stable Log(n) in height
are rotation operations costly ... i mean are they as slow as treaps ?
I do not really like solving problems with AVL, because its just a lot harder to implement than treap. And for the complexity it may be a little faster, but still its harder to implement.