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
| #include <bits/stdc++.h>
#define MAX_N 100010
typedef long long Long;
using namespace std;
int n, m, a[MAX_N];
long long tree[MAX_N * 4];
void build(int k, int s, int t) {
if (s == t) {
tree[k] = a[s];
return;
}
int mid = s + t >> 1;
build(k << 1, s, mid);
build(k << 1 | 1, mid + 1, t);
#define update(k) tree[k] = max(tree[k << 1], tree[k << 1 | 1])
update(k);
}
void modify(int k, int s, int t, int p, int x) {
if (s == t) {
tree[k] += x;
return;
}
int mid = s + t >> 1;
if (p <= mid)
modify(k << 1, s, mid, p, x);
else
modify(k << 1 | 1, mid + 1, t, p, x);
update(k);
}
long long query(int k, int s, int t, int l, int r) {
if (l <= s && t <= r) return tree[k];
int mid = s + t >> 1;
long long ret = -1000000000000LL;
if (l <= mid) ret = max(ret, query(k << 1, s, mid, l, r));
if (mid < r) ret = max(ret, query(k << 1 | 1, mid + 1, t, l, r));
return ret;
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> a[i + 1];
build(1, 1, n);
while (m--) {
int ctrl, i, x, l, r;
cin >> ctrl;
if (ctrl == 0) {
cin >> i >> x;
modify(1, 1, n, i, x);
} else {
cin >> l >> r;
cout << query(1, 1, n, l, r) << "\n";
}
}
return 0;
}
|
