suvro_coder's blog

By suvro_coder, history, 7 months ago, In English,

Can anyone provide me some source to learn treaps which is implemented using arrays. I got some source to understand it from this quora thread https://threads-iiith.quora.com/Treaps-One-Tree-to-Rule-em-all-Part-1 but I'm not getting the code. Some array solution like that of segment trees would have been helpful. Thank you.

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

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

You can't implement treaps implicitly in an array unlike segment trees since treaps are not complete binary trees. You could use array indexing instead of using pointers (i.e. arena allocation), but that would be more complicated. The best way is to use pointers and new to allocate a new node. Check out the CP Algorithms article on treap.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    For a fun I've implemented your idea about array indexed treaps. Here is the solution for URI 2529 without pointers. This solution is a bit slower (about 15%) than a solution with pointers.

    C code