### biximo's blog

By biximo, history, 10 months ago,

I recently came across a very interesting Data Structure, that to me, was completely revolutionary in how I view data structures. That is, Implicit Treaps. But on to my question: Now that I'm pretty familiar with the implementation of Treaps and its applications, should I learn Splay Trees (I will learn it regardless eventually, but I have a competition coming up and time is limited)? To narrow down the question, are there problems that can be solved with Splay Trees but not with Treaps?

Through a brief research session, I found the following blog from CF that partially answers my question. https://codeforces.com/blog/entry/60499 Apparently, Link Cut Trees can be maintained with Splay Trees in N log N time while Treaps have an additional log factor. Are there other instances of this?

• +7

 » 10 months ago, # | ← Rev. 2 →   -10 Splay trees can maintain a sequence of length $n$ supporting reversing a subsequence for $m$ times in $O((n+m) \log n)$ time.
•  » » 10 months ago, # ^ |   +10 Feel free to correct me, but I believe Treaps can as well (using lazy propagation) with a time-complexity of $O(m log n)$. For example, I used a Treap to solve the following problem. https://cses.fi/problemset/task/2074
•  » » » 10 months ago, # ^ |   +10 Additionally, Implicit Treaps support an impressive list of range queries, range updates that it supports (all in $O(logN)$!). For example, I solved UPIT from COCI 2010/2011 using Treaps.
•  » » » 10 months ago, # ^ |   +6 Thank you for your correction. Treap can indeed solve that problem.
 » 10 months ago, # |   0 I think you will be fine with just the treap as most contests do not make problems such that one passes and the other one does not.
•  » » 10 months ago, # ^ |   0 I see. Thank you for your input! I think I will instead direct my time and effort into finally learning the god-dang difficult DNC Optimization.