Hello there
I'm trying to learn treaps and I've been stuck for a while trying to figure out how merge and split functions work
and I've read somewhere that reverse operations on arrays can be done using treaps
any help explaining these topics would be appreciated :D
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
GlebsHP gave a lecture on this two weeks ago, and you can watch it here.
Which lectures are these exactly? Are there any notes etc. available?
It was in the Brazillian ICPC Summer School.
It was just what i needed !!
thank you
If you need a simple implementation of Split and Merge functions, you can check out this code
I have written an article explaining treaps and their applications. Here are the links to Part-1 and Part-2 of the article. Part-1 explains the basic construction of the data structure and its use as Balanced BST's. Part-2 explains implicit treaps and its use as a Dynamic Interval Tree.
Hope that helps :)
the implementation in your blog was perfect thank you
one question comes to mind now ... generating random numbers without collisions ... is it possible ?
if so what is the method used ?
Look, this is my treap implementation — http://ideone.com/8DUWwZ. It's a bit different since it uses rotations instead of merge/split but the generation is the same. I use the structure called xorshift for that, it's a pseudo number generator, you can google it. It produces the same sequence of values every time so you can check if the numbers you choose for x,y,z,w give a collision in the first 10^6 numbers generated and if they don't, you are safe. Actually I haven't seen a case when it produces a collision so if you randomly enter some integers for x,y,z,w, it will most likely give no collision :)
PS: Of course you can simply put all numbers from 1 to 10^6 in a vector, then random shuffle it and always take the last element but random shuffle uses modulo operations and mine doesn't so I will keep using it :)
your xorshift struct is very fast, easy to implement, and with 0 collisions up to 10^7 ... which is how much i was willing to wait for :p
thank you very much ...
question if you may ... handling repeating elements insertion in a treap using the merge/split method where i have repeating elements ... is there a way to have one node for an element and keep a frequency variable in each node ... besides the obvious way of course where i look for it first with a find method ?
I think it can be done by adding a counter in each node and if the key is in the treap just increase it :) Actually I have used the normal treap as MULTIset assuming that left subtree contains nodes with key less than the current and right subtree contains nodes with key greater than or equal to the current. Insert, erase and find worked correctly but not kth and count_less, maybe I had some bug :)
plus another question regarding BSTs in general ... what is the best way to handle duplicates ?
in AVL trees i used to put the frequency in the node itself but i can't see how that's possible here