java segment tree

1// Segment tree class for sum over range
2
3class SegmentTree {
4
5    private int defVal;     // Default value for queries
6    private int arrLen;     // Size of the original array
7    private int[] tree;     // Storage for the data structure
8    
9    /**
10     * Constructor for the Segment Tree
11     * @param arr = the original array
12     */
13    SegmentTree (int[] arr, int defVal) {
14    
15        this.defVal = defVal;
16        arrLen = arr.length;
17        tree = new int[2*arrLen];
18        
19        // Copy elements to the leaf nodes
20        for (int i = 0; i<arrLen; ++i) {
21            tree[i+arrLen] = arr[i];
22        }
23        // Alternative
24        // System.arraycopy(arr, 0, tree, arraySize, arraySize);
25        
26        build();
27    
28    }
29  
30    /** the operation to perform */
31    private int operation (int a, int b) {
32        return a+b;
33    }
34    
35    /** Initialize the inner nodes */
36    public void build() {
37        
38        for (int i = arrLen-1; i>=1; --i) {
39            // Parents are the sum of their children
40            tree[i] = operation(tree[2*i], tree[2*i+1]);
41        }
42    
43    }
44    
45    /**
46     * Update the value at index i to val
47     * @param i = the index to update
48     * @param val = value to be added
49     */
50    void update (int i, int val) {
51        
52        i += arrLen;        // Increment i to its leaf node counterpart
53        tree[i] += val;     // Update the leaf node
54        i /= 2;             // Go to i's parent
55        
56        // Bubble up to i's parents until the root node
57        for (; i>=1; i /= 2) {
58            // Update the parents
59            tree[i] = operation(tree[2*i], tree[2*i+1]);
60        }
61        
62    }
63    
64    /**
65     * Get the sum over the interval [l, r]
66     * @param l = left most index
67     * @param r = right most index
68     * @return sum over [l, r]
69     */
70    int query (int l, int r) {
71        
72        // Increment l and r to their leaf node counterparts
73        l += arrLen;
74        r += arrLen;
75      
76        int sum = defVal;
77    
78        // While l and r are still left and right
79        while (l<=r) {
80            
81            if (l%2==1) {                          // If l is the right child of the parent
82                sum = operation(sum, tree[l]);     // Add the right child to the sum
83                ++l;                               // Make l to the right child of the next branch
84            }
85            
86            if (r%2==0) {                   	   // If r is the left child of its parent
87                sum = operation(sum, tree[r]);     // Add the left child to the sum
88                --r;               				   // Move r to the left child of the next branch
89            }
90          
91            l /= 2, r /= 2;         // traverse to their parents
92        
93        }
94        
95        return sum;
96    
97    }
98
99}