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?
Splay trees can maintain a sequence of length $$$n$$$ supporting reversing a subsequence for $$$m$$$ times in $$$O((n+m) \log n)$$$ time.
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
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.
Thank you for your correction. Treap can indeed solve that problem.
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.
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.