Treap: an elegant Data Structure

Today I'm gonna code a relatively simple and efficient data structure, treap. Basically treap is like a improved Binary Search Tree(BST). Although BST gives lg(n) time performance  on searching and inserting the values but it has a drawback which makes it most of the times impractical. BST could reshape itself in linked list on certain values. To overcome this problem many solutions have been provided like AVL trees, RB(Red-Black) trees, 2-3-4 trees and so on. These trees maintains the height to lg(n) which assures the  lg(n) performance.
   Treap also does the same but in much simple manner. Treap = "Tree" + "Heap". If you've already coded a BST and a heap, treap must be a piece of cake for you. Treap is built on the idea of "Randomized BST". Here randomized means the input for BST is randomly distributed. It doesn't follow any predefined rule. In practice we don't have control over input data so we add the randomness in BST in form the heap priority. Treap nodes have two things, key and priority. Key is used for inserting values exactly as in BST while priority is maintained as in heap. Formally, key of left child should be less than or equal to right child and priority of parent node should be greater than its child nodes.
   Here I've implemented only insert() and delete(). They works as follows:
   Insertion : Insertion in treap works exactly as in BST with the addition that we've to maintain the heap property of nodes. For maintaining the priority in nodes there are two methods, rotateLeft() and rotateRight()
   Deletion : Deletion works in opposite way of insertion. We first locate the node to be deleted and then float it down till it become leaf node and the eventually clip it.

Here's the implementation in Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Random;

class Treap{
    // Nodes in treap
    class Node{
        private int key, priority;
        Node left, right;
        Node( int k){
            this.key = k;
            // this.hashCode() is for uniqueness
            this.priority = this.hashCode();
            left = right = null;
        }
    }

    Node root;

    Treap(){root = null;} // Constructor

    public void insert (int key){
        root = insert (root, key);
    }

    private Node insert (Node dummy, int val){
        if (dummy == null){
            return new Node(val);
        }
        else if (val < dummy.key){
            dummy.left = insert(dummy.left, val);
            if (dummy.left.priority > dummy.priority){
                dummy = rotateRight(dummy);
            }
        }
        else if (val > dummy.key){
            dummy.right = insert(dummy.right, val);
            if (dummy.right.priority > dummy.priority){
                dummy = rotateLeft(dummy);
            }
        }
        return dummy;
    }

    private Node rotateRight (Node dummy){
        Node tmp = dummy.left;
        dummy.left = tmp.right;
        tmp.right = dummy;
        return tmp;
    }

    private Node rotateLeft (Node dummy){
        Node tmp = dummy.right;
        dummy.right = tmp.left;
        tmp.left = dummy;
        return tmp;
    }

    public void printTreap(){
        // in-order traversal as in  BinarySearchTree
        print(root);
    }

    private void print(Node n){
        if (n == null)
            return ;
        else {
            print (n.left);
            System.out.print (n.key+" ");
            print (n.right);
        }
    }

    private boolean findNode (Node dummy, int query){
        while (dummy != null){
            if (query == dummy.key){
                return true;
            }
            if (query < dummy.key)
                dummy = dummy.left;
            else dummy = dummy.right;
        }
        return false;
    }

    public void deleteNode(int key){
        // findNode returns true if node exists otherwise false
        if (findNode(root, key))
            root = remove (root, key);
        else System.out.println ("There's no such key in treap.");
        
    }

    private Node remove (Node dummy, int val){
        if (val < dummy.key)    // to locate the node
            dummy.left = remove(dummy.left, val);
        else if (val > dummy.key)       // to locate the node
            dummy.right = remove(dummy.right, val);

        else {     //  node found
            if ((dummy.left == null && dummy.right == null)||                    
                    dummy == null ) return null;   //clip the leaf node

                // make sure both children exists
            else if (dummy.left != null && dummy.right != null){
                if (dummy.left.priority > dummy.right.priority){
                    dummy = rotateRight (dummy);
                    dummy.right = remove (dummy.right, val);

                }
                else {
                    dummy = rotateLeft (dummy);
                    dummy.left = remove (dummy.left, val);
                }
            }


            else if (dummy.left == null){   // node only having right child
                dummy = rotateLeft (dummy);
                dummy.left = remove (dummy.left, val);
            }
            else if (dummy.right == null){  // node only having left child
                dummy = rotateRight (dummy);
                dummy.right = remove (dummy.right, val);
            }

        }
        return dummy;
    }
}

class testDrive{
    public static void main (String [] S)throws IOException{
        Treap t = new Treap();
        Random gen = new Random();
        for (int i=1;i<10;i++){
            int value = gen.nextInt(100);
            // insert values in treap
            t.insert(value);
        }
        System.out.println("Content of treap");
        t.printTreap();
        System.out.println();

        int num;
        BufferedReader br = new BufferedReader (new InputStreamReader(System.in));
        // to test the deletion in treap
        for (int i=0;i<9;i++){
            num = Integer.parseInt(br.readLine());
            t.deleteNode(num);
            t.printTreap();
            System.out.println();
        }
    }
}

Lazy propagation in Segment Tree

UPDATE 1: I've written a tutorial explaining basics of Segment tree along with example. You can find it at https://techienotes.info/2015/08/31/segment-tree-tutorial/

UPDATE 2: I've re-written this tutorial about lazy propagation. That updated article explains the technique in a much clear manner with a lot of comments in the code. I strongly recommend you to go through the new article. You can find it at https://techienotes.info/2015/09/01/lazy-propagation-in-segment-tree/


Question: An array of integers of $N$ elements from $1$ to $N$ is given. Two types of operations are to be done. You can add or subtract a value in the range of $p$ to $q$ where $1\le{p,q}\le{N}$ or you can ask for sum of elements between range of $p$ to $q$.


Solution: One can go for bruteforce but it is too slow. Suppose there are $T$ operations and each operation would require $O(n)$ in worst case for a loop $p$ to $q$. This approach leads to $O(T\cdot{N})$ complexity. If $T$ and $N$ both are $10^6$, this will lead to $O(10^{12})$ which isn't acceptable. However, this problem could be solved by other approaches like BIT(Binary Indexed Trees) and so on. I'm going to solve it by Segment Trees based on arrays. This array based Segment tree consumes more memory but it's easy to implement.
 I assume you know at least how to build a Segment Tree. Suppose initially all the elements of array are zero and that's why we don't have to build it explicitly. We can start updating it. What I'm using to update the range is either lazy propagation or something very similar to it. Well whatever it is, here's the idea.
For a given range find that parent node close to root as much as possible which includes the given range completely. Now update this node with value$\times$range of this node. Range of this node means the range of array for which this node is responsible. After this, we set a flag on it. Idea behind flag is that this range will be updated when the query for sum will be fired. When there is query for sum of a range, we start with root and proceed downwards the tree. If flag is set on any node, value of this node will be updated and flag will be passed on to its children, i.e flag of this node will unset and will be set on its children. In this procedure of finding sum we update only those nodes which we encounter in our range. 
Things become easy with example, so let's take this one. 

Problem Statement: http://www.spoj.pl/problems/HORRIBLE/
Here's my code:

import java.io.BufferedReader;
import java.io.IOException;
import java.util.Arrays;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class horrible{
    private static long tree[], helper[];
    private static boolean color[];

    public static void main (String [] args) throws IOException{
        BufferedReader br = new BufferedReader (new InputStreamReader (System.in));
        StringTokenizer st =null;
        int t = Integer.parseInt(br.readLine());
        for(;t>0;t--){
            st = new StringTokenizer (br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int C = Integer.parseInt(st.nextToken());
            init(N);
            for (int I=1;I<=C;I++){
                st = new StringTokenizer(br.readLine());
                if (st.nextToken().equals("0")){
                    int P = Integer.parseInt(st.nextToken());
                    int Q = Integer.parseInt(st.nextToken());
                    long V = Long.parseLong(st.nextToken());
                    update (1,1, N, P,Q, V);
                }
                else {
                    int P = Integer.parseInt(st.nextToken());
                    int Q = Integer.parseInt(st.nextToken());
                    long ans = sum_of_range (1,1,N, P,Q);
                    System.out.println(ans);
                }
            }
        }
    }

    private static void init(int N){
        tree = new long [262145];
        helper = new long [262145];
        color  = new boolean [262145];
        Arrays.fill (tree,0);
        Arrays.fill (helper, 0);
        Arrays.fill (color, false);
    }

    private static   void update (int node, int start, int end, int left, int right, long value){
        if (left > end || right <start )
            return ;
        if (start == end ){
            tree[node]+= value;
            if (color[node]==true){
                tree[node] += helper[node];
                helper[node]=0;
            }
            return;
        }
        if (left <=start && right >= end){
            helper[2*node] += value;
            helper[2*node+1] += value;
            color[2*node] = color[2*node+1] = true;
            tree[node] += (value *(end-start+1));
            return ;
        }
        else if (left <= end && right >end)
            tree[node ] += (value*(end-left+1));
        else if (start <= right && left <start)
            tree[node] += (value*(right-start+1));
        else if (left >= start && right <= end)
            tree[node] += (value*(right-left+1));

        update (2*node, start, (start+end)/2, left, right, value);
        update ((2*node)+1, ((start+end)/2)+1, end, left, right, value);
        return;
    }


    private static long sum_of_range (int node, int start, int end, int left, int right){
        if (left > end || right <start)
            return 0;
        if (color[node] == true){
            tree[node] += (helper[node] *(end-start+1));
            color[node]=false;
            if (start != end){
                color[2*node]=color[2*node+1] = true;
                helper[2*node] += helper[node];
                helper[2*node+1] += helper[node];
            }
            helper[node]=0;
        }
        if (left <= start && right >= end){
            return tree[node];
        }
        long s1 = sum_of_range(2*node, start, (start+end)/2, left, right);
        long s2 = sum_of_range(2*node+1,((start+end)/2)+1,end, left,right);
        return s1+s2;
    }
}

First of all, size of tree which is $262145$ isn't random figure. We build a segment tree for a given array with with $N$ leaf nodes. For a binary tree with $N$ leaf nodes its height would be $\lceil(\log_2N)\rceil$. So we need space of tree$[2^{\lceil(\log_2N)\rceil + 1}]$.Here $+1$ is because at $n^{th}$ level of binary tree number of elements is almost equal to the number of all nodes from root node to (n-1)th level in worst case so you need one extra level of height. In this case $N = 10^5$, $\lceil(\log_210^5)\rceil+1 = 18$ and $2^{18} = 262144$. Well here figure is $262145$, it's because in my practice. I prefer to allocate one more element to reduce off-by-one errors. Next, there are two other arrays helper and color. color is a boolean array to set/unset the flag on node and helper array is for storing the values in buffer until a query for sum is fired. e.g. there are five consecutive update queries and there is a node which is part of all of these queries. Suppose the five queries were to update the range by $2, 4, 1, 6, 3$. Now for every update query these values will added to helper. After these queries helper[node] will have value of $2+4+1+6+3=16$ assuming initially it was zero. Say, sixth query is for sum. Now, for e.g. if this node has range $6$ to $10$ then after sum query it will be $16\times(10-6+1) = 80$. $10-6+1$ is because this node is responsible for array element $6,7,8,9$ and $10$; a total of five elements. Do not forget to set the helper[node] to $0$ after updation. This approach is called lazy because any node won't be updated until it's needed. The values propagates from root to leaf nodes in lazy way.
Rest of the details could be easily figured out in the code itself. If something isn't clear, please leave a comment.