sdssudhu's blog

Can MKTHNUM be solved with treap ?
By sdssudhu, history, 6 years ago, In English

I was learning about treap sometime back and I was trying a few problems today. Now I am wondering if MKTHNUM can be solved using a treap. And if possible can insertion queries also be handled with it ??

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Well if you have only insertion queries — yes but it will be offline. Simply consider the insertions in reverse order. This way the insertions will become erases and it can be easily solved with Merge Sort tree with Treap or any other BST.

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

    Can you elaborate a bit more on the deletion part and how it can be implemented with merge sort tree?? Thanks

    → Reply