As a way to solve Problem E from ZeptoLab Code Rush 2014, I decided to implement Treap for the first time. Treap is a randomized binary search tree that the maximum height of the tree is about O(log n) (similar to AVL tree). It's easier to implement than a normal AVL tree. Why do I have to implement it? I need to perform these operations in O(log n): Add, Remove, Find the sum of the k smallest elements. My implementation was added here.
Note that this problem E can also be solved by other data structures: Binary Indexed Tree, Cartesian tree or Priority Queue, because this problem only requires calling this operation, "Find the sum of the k smallest elements", multiple times with the non-ascending value of k.
No comments:
Post a Comment