SecondThread's blog

Algorithms Thread 9: Treaps (+ Gym Contest!)
By SecondThread, history, 4 years ago, In English

Algorithms Thread Episode 9: Treaps

Good morning everyone!

Episode 9 of AlgorithmsThread comes out shortly after the Div2 round ends. This episode is on Treaps! It covers:

  • Fundamentals of Treaps
  • Splitting and Merging
  • Range reversing

... and more! I also decided to keep up the super-high quality style and made a custom gym set with 5(+2) original problems to make sure you really understand everything that was covered in the lecture. The gym set will be released shortly after the lecture ends, and I hope that the problems will be challenging and fun, even for people who aren't seeing treaps for the first time.

If you have any questions or suggestions, feel free to leave them below. I hope you enjoy the problem statements, and, in the spirit of the upcoming holiday, I'll leave you all with this:

Update: The scoring distribution for this round will be: 1 — 1 — 1 — 1 — (+1) — (+1) — 1

Update2: Solution video is out now and solutions to all problems are available here. Hope you all enjoyed the contest!

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

Comments Comments (57)
| Write comment?
»
4 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Your last tutorial was very good (Algorithms thread : Tree basic), now i cann't wait for this one anymore. thank you.

→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I was sad at first because u didn't participated in today's contest as it was really an interesting one, but after watching this post, omg made my day :)

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I wonder if SecondThread just missed today's div2 contest like I did since we are so used to the starting time of XX:35AM. :)))

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +66 Vote: I do not like it

    I was up all night making sure there weren't bugs in the judge solutions actually. One of them was broken and I fixed it now (hopefully everything else is okay haha)

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Damn, no wonder you can participate contest starting at 2:00AM our time. Really appreciate your efforts, hopefully you'll catch up some nice sleep soon.

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +22 Vote: I do not like it

      Thanks a lot, David. That's a lot of effort you do for us, beginners and enthusiasts. Especially, when you also have a job, as well as make regular screen-cast of CF rounds participate side-by-side.

      → Reply
»
4 years ago, # |
  Vote: I like it +134 Vote: I do not like it

This is great! One possible improvement for your gym contests is sample explanations, consider creating those more often.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -45 Vote: I do not like it

    Has he asked for your advice ? He is at least doing CP related things instead people like you who just make useless blogs , comments , doing Leetcode/interview problems for getting more contribution and low rated subscribers . He deserves to be on top of contribution list not you.

    → Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Unrelated, but I was kind of scared when you brought an axe infront of that nice little tree in your beautiful episode...In any case, learned a lot of new concepts from your fabulous video. Waiting for the custom gym.

→ Reply
»
4 years ago, # |
  Vote: I like it +28 Vote: I do not like it

The classic "Good Morning, Everyone" by SecondThread!!

→ Reply
»
4 years ago, # |
  Vote: I like it +28 Vote: I do not like it

imagine not using splay trees #SplayGang

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Splay will break in case you need persistence

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      randomly splay a couple elements and call it a day

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it +16 Vote: I do not like it

        I think rpeng and Friends actually came up with a legit way of handling this. It has something to do with splaying if you ever reach 4*log(n) height I think, but he would be able to explain it much better than I could.

        Of course, you can just use treaps too, which is probably way easier in this case.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +11 Vote: I do not like it

          i wonder what would happen if you kept track of the longest path in the tree, and then splayed the deepest node a bunch of times before you start keeping track of the roots for persistence.

          → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +16 Vote: I do not like it

          Paging Darooha, I think his theory was to take all the nodes that are too deep, and splay a few extra per iter or something.

          I think the constant factor overhead of this is massive though.

          The bigger issue is I don't know problems that force persistent BSTs: usually some kind of 2~3 layer bucketing works just as well for them (and are probably just as silly to code). Are there such problems with tight resource constraints?

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it +10 Vote: I do not like it

            Sorry for the necropost. I think Поиск идеи by izban is a great task to benchmark persistent BST. For that task, I heard persistent treap fails because of tight ML (which is 1GB lol). Intended solution uses persistent 2-3 trees.

            As for the thread in general, I also only know how to use splay trees, but the issue with persistency made me to seriously consider learning other BBSTs. I'm also bad at implementing splay trees, so I wonder if learning treaps will make my life easier.

            → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +11 Vote: I do not like it

          Sounds similar to scapegoat to me.

          → Reply
»
4 years ago, # |
  Vote: I like it +25 Vote: I do not like it

been postponing even the thought of reading about treaps for god knows how many years xD

Now I can finally have a proper intro, thanks for the help!

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Though it's my first participation, I am really excited with the episodes. Happy Halloween !

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

SecondThread, Afaik I remember, you said that when you create Treap on N numbers, you create N Nodes and then merge them. But when merge is done, it is assumed that all elements on the left treap is smaller than the numbers on the right Treap and merging is done only on the basis of priority. But if I were to make a Treap on unsorted array, then the inorder traversal of the array wont give a sorted representation of the array. Is there an inconsistency or have I miss understood something???

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    you assume the keys on the left are smaller than the keys on the right when doing a merge. in the case of an array, the keys are the indices, not the values in the array.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Still my point sustains, (in his implementation) we are not creating the treap based on the key but using the priorities (at least while merging). My understanding says, the inorder of treap should give sorted array, and the priorities helps in maintaining the height of treap of order O(logn). I dont see the key being used to create the treap.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        treap is heap on priorities + BST on keys. you use both properties

        → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    It is okay that the inorder traversal of the treap isn't actually a sorted array. When you do merges, you keep the stuff that is on the left on the left, and the stuff on the right on the right, so you can force the left-right order to be whatever you want. The top-bottom order is randomized to keep it log-n tall. Does that make sense?

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good!

→ Reply
»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Why were half of the problems deleted D:

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it possible to do "treap-beats?" More specifically, is it possible to do the segtree-beats operations, such as range-mod updates and range-sum queries, on a treap? (while still allowing for standard split/merge ops on a treap)

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    It sure is! Remember when I said that "Anything you can do with segment trees you can also do with Treaps"? That includes all the cool segment tree tricks like persistance and STBeats!

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Two more questions about segtrees vs treaps :)

      • In some segtree problems, you want to store a data structure, such as a CHT, over all of the nodes in that range. For example, an approach to this problem would be to store a segment tree of CHT's. Because each node in the segment tree could have up to O(n) children, would it also be possible to do this with a treap, as in a treap you might need to recalc a node many times?

      • Also, are there 2-d treaps? Sorry if it's not a great question, but I can't really think of a good way to implement it.

      Thanks for the help!

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

Could someone provide a hint for the "Grim Treaper" problem? Doing all types of queries is simple but maintaining the sum is actually tricky :D

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Well, I haven't coded it up yet, but I guess the solution is

    Guess at solution
    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I AC'd with this approach, but I wonder what the time complexity is.

      Spoiler
      → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +10 Vote: I do not like it

      Thanks a lot for the solution. I haven't know "the segment beats" technique before (should have checked all the AlgoThread videos). If someone else is interested what it is, check the video or this amazing blog post.

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can someone share test case 3 of this problem? I'm getting WA :(

    → Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it +43 Vote: I do not like it

There are a couple things that should be fixed in SecondThread's c++ treap template on his github:

  1. There is a missing parentheses in the "rangeAdd" function
  2. The value "data" isn't set in the constructor
  3. Vectors are used everywhere. This slows down the code a lot (because of the huge vector overhead). Just changing the vectors to std::array helped reduce the runtime of my D solution by a couple of seconds.

Thanks!

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I would like to know if the last problem (problem Z: trick or treap) could be solved using splay tree..., anyone could solve this problem using splay tree?. If its possible, I would really like to discuss about it after the contest end

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I briefly mentioned this in the video, but really the only purpose of a treap is to keep your trees shallow. Treaps do it nondeterministicly which makes it easy to code, but there are other things you can do like a splay tree or red black tree that work too. So basically yes, pretty much everything* that is possible with a treap is also possible with a splay tree if you want.

    *things that use persistent treaps might have a faster runtime than persistent splay trees in theory, but there are likely workarounds in that one case. The reason this is different is that splay trees are amortized to log, but that amortization isn't taken into account if you make it persistent.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I solved it using splaytrees. You can probably check my code out after the end of the contest.

    → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Can anyone give some hints on B and Z? Thanks in advance!

UPD: solved B using string hashing.

UPD2: solved Z by maintaining parent nodes.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I tried to implement this on B but I couldn't.

    How did you store and update the indexes on each node in the treap? did you use lazy propagation?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      No need for lazy propagation. Just store the hashing value for the original string and the reversed string.

      node updating
      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It's true!

        I didn't thought that way, this is really cool.

        thank you very much for the explanation :)

        → Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Did someone manage implement the C++ code from the GitHub, for some reason I get wrong answer on test case 8 on the first problem, and cannot see the test case in order to debug.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    Yeah I just saw there was a small mistake in C++ code. SecondThread forgot to set toProp to 0 which causes kind of undefined behaviour.

    You can even remove it because it's not needed. Also removed from your code some unneeded things like sum, toProp, used mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); only once and time improved from 4400ms to 2500ms. You could also, instead of splitting the tree to get the value at some position, use that fact, that traversal of the tree from left to right is the left to right traversal of the array.

    left to right traversal:
    → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

In Problem C, I got 15 TLE on test 15. My solution is treap with lazy-tags.
- Tags 1: flip each node on the subtree
- Tags 2: reverse the subtree
- Tags 3 = Tags 1 + Tags 2
- Tags 4/5: set each node = 0/1
Is that right? or how can I solve this problem?
last submission: 97961309

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    I've found my bug, I used value instead of rand-key when merging. Thanks!!!

    → Reply
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Auto comment: topic has been updated by SecondThread (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is test case 19 on problem Z?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

SecondThread Does it matter to split with the condition key < node.value or key <= node.value ?

I'm solving CF Education Round 15 F, If I use key < node.value, I am getting AC, If I use key <= node.value, I am getting TLE.

Any idea why would that happen?

Also does different ways insert function affect the running time a lot? I'm getting AC if I use

void insert(pitem &t, pitem it){
    pitem l, r;
    split(t, l, r, it->value);
    merge(t, l, it);
    merge(t, t, r);
}

But TLE if I use 

void insert(pitem &t, pitem it){
    push(t);
    if(!t) t = it;
    else if(it->prior > t->prior) split(t, it->l, it->r, it->value), t=it;
    else insert(t->value <= it->value ? t->r : t->l, it);
}

I'm not understanding why? Can you please help me?

→ Reply