same parent-child relationship that they did prior to the insertion of the middle number. In a randomized binary search tree, the tree after the deletion is equally likely to be either of the two possible trees on its two nodes, independently of what the tree looked like prior to the insertion of the middle number. Implicit treap An implicit treap is a simple variation of an ordinary treap which can be viewed as a dynamic array that supports the following operations in : Inserting an element in any position Removing an element from any position Finding sum, minimum or maximum element in a given range. Addition, painting in a given range Reversing elements in a given range The idea behind an implicit treap is to use the array index as a key, but to not store it explicitly. Otherwise, an update (insertion/deletion) would result in changes of the keys in nodes of the tree. The key value (implicit key) of a node T is the number of nodes less than that node plus one. Note that such nodes can be present not only in its left subtree but also in left subtrees of its ancestors P, if T is in the right subtree of P. Therefore we can quickly calculate the implicit key of the current node as we perform an operation by accumulating the sum of all nodes as we descend the tree. Note that this sum does not change when we visit the left subtree but it will increase by when we visit the right subtree. The join algorithm for an implicit treap is as follows:void join (pitem & t, pitem l, pitem r) { if (!l || !r) t = l ? l : r; else if (l->prior > r->prior) join (l->r, l->r, r), t = l; else join (r->l, l, r->l), t = r; upd_cnt (t); } The split algorithm for an implicit treap is as follows:void split (pitem t, pitem & l, pitem & r, int key, int add = 0) { if (!t) return void( l = r = 0 ); int cur_key = add + cnt(t->l); //implicit key if (key <= cur_key) split (t->l, l, t->l, key, add), r = t; else split (t->r, t->r, r, key, add + 1 + cnt(t->l)), l = t; upd_cnt (t); } Operations Insert element To insert an element at position pos we divide the array into