-
Notifications
You must be signed in to change notification settings - Fork 0
/
SegmentTree.java
113 lines (91 loc) · 2.35 KB
/
SegmentTree.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
111
112
113
package data_structures.trees;
import java.util.Scanner;
// Range Sum Query (with lazy propagation)
public class SegmentTree { // 1-based DS, OOP
int N; //the number of elements in the array as a power of 2 (i.e. after padding)
int[] array, sTree, lazy;
SegmentTree(int[] in)
{
array = in; N = in.length - 1;
sTree = new int[N<<1]; //no. of nodes = 2*N - 1, we add one to cross out index zero
lazy = new int[N<<1];
build(1,1,N);
}
void build(int node, int b, int e) // O(n)
{
if(b == e)
sTree[node] = array[b];
else
{
int mid = b + e >> 1;
build(node<<1,b,mid);
build(node<<1|1,mid+1,e);
sTree[node] = sTree[node<<1]+sTree[node<<1|1];
}
}
void update_point(int index, int val) // O(log n)
{
index += N - 1;
sTree[index] += val;
while(index>1)
{
index >>= 1;
sTree[index] = sTree[index<<1] + sTree[index<<1|1];
}
}
void update_range(int i, int j, int val) // O(log n)
{
update_range(1,1,N,i,j,val);
}
void update_range(int node, int b, int e, int i, int j, int val)
{
if(i > e || j < b)
return;
if(b >= i && e <= j)
{
sTree[node] += (e-b+1)*val;
lazy[node] += val;
}
else
{
int mid = b + e >> 1;
propagate(node, b, mid, e);
update_range(node<<1,b,mid,i,j,val);
update_range(node<<1|1,mid+1,e,i,j,val);
sTree[node] = sTree[node<<1] + sTree[node<<1|1];
}
}
void propagate(int node, int b, int mid, int e)
{
lazy[node<<1] += lazy[node];
lazy[node<<1|1] += lazy[node];
sTree[node<<1] += (mid-b+1)*lazy[node];
sTree[node<<1|1] += (e-mid)*lazy[node];
lazy[node] = 0;
}
int query(int i, int j)
{
return query(1,1,N,i,j);
}
int query(int node, int b, int e, int i, int j) // O(log n)
{
if(i>e || j <b)
return 0;
if(b>= i && e <= j)
return sTree[node];
int mid = b + e >> 1;
propagate(node, b, mid, e);
int q1 = query(node<<1,b,mid,i,j);
int q2 = query(node<<1|1,mid+1,e,i,j);
return q1 + q2;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int N = 1; while(N < n) N <<= 1; //padding
int[] in = new int[N + 1];
for(int i = 1; i <= n; i++)
in[i] = sc.nextInt();
sc.close();
}
}