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}