【模板】树状数组1(单点修改，区间查询)
原题链接
题目详情
算法与思路
这是一道裸模板题，只需要根据前文所讲的操作写一遍即可。
代码
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 | #include <bits/stdc++.h>
using namespace std;
const int N = 500010;
int n, m;
int tr[N];
inline int lowbit(int x) {
return x & -x;
}
inline void add(int x, int k) {
for (int i = x; i <= n; i += lowbit(i))
tr[i] += k;
}
inline int sum(int x) {
int res = 0;
for (int i = x; i; i -= lowbit(i))
res += tr[i];
return res;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
int x; cin >> x;
add(i, x);
}
int op, x, y;
while (m--) {
cin >> op >> x >> y;
if (op == 1) add(x, y);
else cout << sum(y) - sum(x - 1) << '\n';
}
return 0;
}
|
运行结果
