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