two subsections [0...pos-1] and [pos..sz] by calling the split function and we get two trees and . Then we merge with the new node by calling the join function. Finally we call the join function to merge and . Delete element We find the element to be deleted and perform a join on its children L and R. We then replace the element to be deleted with the tree that resulted from the join operation. Find sum, minimum or maximum in a given range To perform this calculation we will proceed as follows: First we will create an additional field F to store the value of the target function for the range represented by that node. we will create a function that calculates the value F based on the values of the L and R children of the node. We will call this target function at the end of all functions that modify the tree, i.e., split and join. Second we need to process a query for a given range [A..B]: We will call the split function twice and split the treap into which contains , which contains , and which contains . After the query is answered we will call the join function twice to restore the original treap. Addition/painting in a given range To perform this operation we will proceed as follows: We will create an extra field D which will contain the added value for the subtree. We will create a function push which will be used to propagate this change from a node to its children. We will call this function at the beginning of all functions which modify the tree, i.e., split and join so that after any changes made to the tree the information will not be lost. Reverse in a given range To show that the subtree of a given node needs to be reversed for each node we will create an extra boolean field R and set its value to true. To propagate this change we will swap the children of the node and set R to true for all of them. See also Finger search References External links Collection of treap references and info by Cecilia Aragon Open Data Structures - Section 7.2 - Treap: A Randomized Binary Search Tree, Pat Morin Animated treap Randomized binary search trees. Lecture notes from a course by Jeff Erickson at UIUC. Despite the title,