forked from sPredictorX1708/Ultimate-Java-Resources
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSegmentTree101.java
More file actions
84 lines (57 loc) · 2.17 KB
/
SegmentTree101.java
File metadata and controls
84 lines (57 loc) · 2.17 KB
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
import java.util.*;
public class SegmentTree101 {
static void createTree(int[] inp ,int[] tree, int start ,int end , int treeNodeIndex){
if(start == end){
tree[treeNodeIndex] = inp[start];
return;
}
int mid = (start+end)/2;
createTree(inp,tree,start,mid,2*treeNodeIndex);
createTree(inp,tree,mid+1,end,(2*treeNodeIndex)+1);
tree[treeNodeIndex] = tree[treeNodeIndex*2] + tree[treeNodeIndex*2+1];
}
static void updateTree(int[] inp, int[] tree,int start , int end , int treeNodeIndex , int idx , int value){
if(start==end){
// we have reached the node that needs to be changed
tree[treeNodeIndex] = value;
return;
}
int mid = (start + end) / 2 ;
if(idx > mid){
// going towards the right subtree
updateTree(inp,tree,mid+1,end,2*treeNodeIndex+1,idx,value);
}else{
// going towards the left subtree
updateTree(inp,tree,start,mid,2*treeNodeIndex,idx,value);
}
tree[treeNodeIndex] = tree[2*treeNodeIndex] + tree[2*treeNodeIndex + 1];
}
static int query(int[] tree,int start , int end , int treeNodeIndex , int left , int right){
// range is completely out of given NodeIndex
if(right < start || end < left){
return 0;
}
// completely inside the given Node Range
if(start>=left && end<=right){
return tree[treeNodeIndex];
}
// partially inside ans Partially outside the given Range
int mid = (start + end)/2 ;
int ans1 = query(tree,start,mid,2*treeNodeIndex,left,right);
int ans2 = query(tree,mid+1,end,2*treeNodeIndex+1,left,right);
return ans1+ans2 ;
}
public static void main(String[] args) {
Scanner fs = new Scanner(System.in);
int n = fs.nextInt();
int inp[] = new int[n];
int tree[] = new int[4*n];
for(int i=0 ; i<n ; i++){
inp[i] = fs.nextInt();
}
createTree(inp,tree,0,n-1,1);
for(int i=0 ; i<4*n ; i++){
System.out.println(tree[i]);
}
}
}