-
Notifications
You must be signed in to change notification settings - Fork 106
/
segmenttreeobj.cpp
73 lines (57 loc) · 1.43 KB
/
segmenttreeobj.cpp
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
int n;
int a[N], b[N];
//
struct SegTree
{
int N;
vector<int> st;
void init(int n)
{
N = n;
st.resize(4 * N + 5);
}
void Build(int node, int L, int R)
{
if (L == R)
{
st[node] = b[L];
return;
}
int M = (L + R) / 2;
Build(node * 2, L, M);
Build(node * 2 + 1, M + 1, R);
st[node] = max(st[node * 2], st[node * 2 + 1]);
}
void Update(int node, int L, int R, int pos, int val)
{
if (L == R)
{
st[node] += val;
return;
}
int M = (L + R) / 2;
if (pos <= M)
Update(node * 2, L, M, pos, val);
else
Update(node * 2 + 1, M + 1, R, pos, val);
st[node] = max(st[node * 2], st[node * 2 + 1]);
}
int Query(int node, int L, int R, int i, int j)
{
if (j < L || i > R)
return 0;
if (i <= L && R <= j)
return st[node];
int M = (L + R) / 2;
return max(Query(node * 2, L, M, i, j), Query(node * 2 + 1, M + 1, R, i, j));
}
int query(int l, int r) { return Query(1, 1, N, l, r); }
void update(int pos, int val) { Update(1, 1, N, pos, val); }
void build() { Build(1, 1, N); }
};
SegTree seg;
void solve()
{
seg.init(4 * n);
seg.build();
}