biximo's blog

By biximo, history, 8 months ago, In English

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?

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
8 months ago, # |
Rev. 2   Vote: I like it -10 Vote: I do not like it

Splay trees can maintain a sequence of length $$$n$$$ supporting reversing a subsequence for $$$m$$$ times in $$$O((n+m) \log n)$$$ time.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      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.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Thank you for your correction. Treap can indeed solve that problem.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.