-
Notifications
You must be signed in to change notification settings - Fork 39
/
Segment Tree.java
80 lines (62 loc) · 1.87 KB
/
Segment Tree.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
class SegmentTree
{
int st[]
SegmentTree(int arr[], int n)
{ int x = (int) (Math.ceil(Math.log(n) / Math.log(2))); int max_size = 2 * (int) Math.pow(2, x) - 1;
st = new int[max_size]
constructSTUtil(arr, 0, n - 1, 0);
}
int getMid(int s, int e) {
return s + (e - s) / 2;
}
int getSumUtil(int ss, int se, int qs, int qe, int si)
{ if (qs <= ss && qe >= se)
return st[si]; if (se < qs || ss > qe)
return 0; int mid = getMid(ss, se);
return getSumUtil(ss, mid, qs, qe, 2 * si + 1) +
getSumUtil(mid + 1, se, qs, qe, 2 * si + 2);
}
void updateValueUtil(int ss, int se, int i, int diff, int si)
{ if (i < ss || i > se)
return;
st[si] = st[si] + diff;
if (se != ss) {
int mid = getMid(ss, se);
updateValueUtil(ss, mid, i, diff, 2 * si + 1);
updateValueUtil(mid + 1, se, i, diff, 2 * si + 2);
}
}
void updateValue(int arr[], int n, int i, int new_val)
{
if (i < 0 || i > n - 1) {
System.out.println("Invalid Input");
return;
} int diff = new_val - arr[i]; arr[i] = new_val; updateValueUtil(0, n - 1, i, diff, 0);
}
int getSum(int n, int qs, int qe)
{
if (qs < 0 || qe > n - 1 || qs > qe) {
System.out.println("Invalid Input");
return -1;
}
return getSumUtil(0, n - 1, qs, qe, 0);
}
int constructSTUtil(int arr[], int ss, int se, int si)
{ if (ss == se) {
st[si] = arr[ss];
return arr[ss];
}
int mid = getMid(ss, se);
st[si] = constructSTUtil(arr, ss, mid, si * 2 + 1) +
constructSTUtil(arr, mid + 1, se, si * 2 + 2);
return st[si];
}
public static void main(String args[])
{
int arr[] = {1, 3, 5, 7, 9, 11};
int n = arr.length;
SegmentTree tree = new SegmentTree(arr, n);
System.out.println("Sum of values in given range = " +
tree.getSum(n, 1, 3)); tree.updateValue(arr, n, 1, 10); System.out.println("Updated sum of values in given range = " +
tree.getSum(n, 1, 3));
}