Algorithm-and-Data-Structure/DataStructure/SegmentTree.java at master · lemidia/Algorithm-and-Data-Structure · GitHub

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
publicclassSegmentTree {
staticlonginit(longsegmentTree[], longarr[], intnode, intstart, intend){
if(start == end)
returnsegmentTree[node] = arr[start];

intmid = (start+end)/2;
returnsegmentTree[node] = init(segmentTree, arr, node*2, start, mid)
 + init(segmentTree, arr, node*2+1, mid+1, end);

 }
staticvoidupdate(longsegmentTree[], intnode, intindex, intstart, intend, longdiff){
// 범위 밖
if(index < start || index > end )
return;
segmentTree[node] += diff;
if(start != end){
intmid = (start+end)/2;
update(segmentTree, node*2, index, start, mid, diff);
update(segmentTree, node*2+1, index, mid+1, end, diff);
 }
 }

staticlongsum(longsegmentTree[], intnode, intleft, intright, intstart, intend){
// 범위 밖 질의
if(right < start || left > end)
return0;

// 완전히 포함하는 질의
if(left <= start && end <= right)
returnsegmentTree[node];

// 그 외, 걸치는 범위 질의
intmid = (start+end)/2;
returnsum(segmentTree, node*2, left, right, start, mid) +
sum(segmentTree, node*2+1, left, right, mid+1, end);
 }

staticdoublebaseLog(doublex, doublebase){
returnMath.log(x) / Math.log(base);
 }

publicstaticvoidmain(String[] args) {
longarr[] = {4,7,1,3,9,5,9,2,4};
intN = arr.length;

inth = (int)Math.ceil(baseLog(N, 2));
longsegmentTree[] = newlong[1<<(h+1)];
// Construct Segment Tree
init(segmentTree, arr, 1, 0, N-1);

// 4 + 7 + 1 + 3 = 15
System.out.println(sum(segmentTree, 1, 0, 3, 0, N-1));
// update index(1) as 10. So, we will decide diff as 3.
update(segmentTree, 1, 1, 0, N-1, 3);
// 4 + 10 = 14
System.out.println(sum(segmentTree, 1, 0, 1, 0, N-1));
 }
}