This repository has been archived by the owner on Oct 29, 2020. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 180
/
SegmentTrees.java
110 lines (97 loc) · 3.31 KB
/
SegmentTrees.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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
public class SegmentTree
{
private int[] tree;
private int maxsize;
private int height;
private final int STARTINDEX = 0;
private final int ENDINDEX;
private final int ROOT = 0;
public SegmentTree(int size)
{
height = (int)(Math.ceil(Math.log(size) / Math.log(2)));
maxsize = 2 * (int) Math.pow(2, height) - 1;
tree = new int[maxsize];
ENDINDEX = size - 1;
}
private int leftchild(int pos)
{
return 2 * pos + 1;
}
private int rightchild(int pos)
{
return 2 * pos + 2;
}
private int mid(int start, int end)
{
return (start + (end - start) / 2);
}
private int getSumUtil(int startIndex, int endIndex, int queryStart, int queryEnd, int current)
{
if (queryStart <= startIndex && queryEnd >= endIndex )
{
return tree[current];
}
if (endIndex < queryStart || startIndex > queryEnd)
{
return 0;
}
int mid = mid(startIndex, endIndex);
return getSumUtil(startIndex, mid, queryStart, queryEnd, leftchild(current))
+ getSumUtil( mid + 1, endIndex, queryStart, queryEnd, rightchild(current));
}
public int getSum(int queryStart, int queryEnd)
{
if(queryStart < 0 || queryEnd > tree.length)
{
return -1;
}
return getSumUtil(STARTINDEX, ENDINDEX, queryStart, queryEnd, ROOT);
}
private int constructSegmentTreeUtil(int[] elements, int startIndex, int endIndex, int current)
{
if (startIndex == endIndex)
{
tree[current] = elements[startIndex];
return tree[current];
}
int mid = mid(startIndex, endIndex);
tree[current] = constructSegmentTreeUtil(elements, startIndex, mid, leftchild(current))
+ constructSegmentTreeUtil(elements, mid + 1, endIndex, rightchild(current));
return tree[current];
}
public void constructSegmentTree(int[] elements)
{
constructSegmentTreeUtil(elements, STARTINDEX, ENDINDEX, ROOT);
}
private void updateTreeUtil(int startIndex, int endIndex, int updatePos, int update, int current)
{
if ( updatePos < startIndex || updatePos > endIndex)
{
return;
}
tree[current] = tree[current] + update;
if (startIndex != endIndex)
{
int mid = mid(startIndex, endIndex);
updateTreeUtil(startIndex, mid, updatePos, update, leftchild(current));
updateTreeUtil(mid+1, endIndex, updatePos, update, rightchild(current));
}
}
public void update(int update, int updatePos, int[] elements)
{
int updatediff = update - elements[updatePos] ;
elements[updatePos] = update;
updateTreeUtil(STARTINDEX, ENDINDEX, updatePos, updatediff, ROOT);
}
public static void main(String...arg)
{
int[] elements = {1,3,5,7,9,11};
SegmentTree segmentTree = new SegmentTree(6);
segmentTree.constructSegmentTree(elements);
int num = segmentTree.getSum(1, 5);
System.out.println("the num is " + num);
segmentTree.update(10, 5,elements);
num = segmentTree.getSum(1, 5);
System.out.println("the num is " + num);
}
}