给定 $n$ 个数组成的一个数列,规定有两种操作,一是修改某个元素,二是求子数列 $[a,b]$ 的连续和。
输入格式
第一行包含两个整数 $n$ 和 $m$,分别表示数的个数和操作次数。
第二行包含 $n$ 个整数,表示完整数列。
接下来 $m$ 行,每行包含三个整数 $k,a,b$ ($k = 0$,表示求子数列$[a,b]$的和;$k=1$,表示第 $a$ 个数加 $b$)。
数列从 $1$ 开始计数。
输出格式
输出若干行数字,表示 $k = 0$ 时,对应的子数列 $[a,b]$ 的连续和。
数据范围
$1 \le n \le 100000$,
$1 \le m \le 100000$,
$1 \le a \le b \le n$,
数据保证在任何时候,数列中所有元素之和均在 int 范围内。
输入样例:
10 5
1 2 3 4 5 6 7 8 9 10
1 1 5
0 1 3
0 4 8
1 7 5
0 4 8
输出样例:
11
30
35
#include <vector>
#include <iostream>
using namespace std;
template<typename T, int SIZE>
class BIT {
private:
vector<T> tr;
int n;
int lowbit(int x) {
return x & -x;
}
public:
BIT() : n(SIZE + 1) {
tr.resize(n);
}
void add(int x, T v) {
for (int i = x; i <= SIZE; i += lowbit(i)) tr[i] += v;
}
T query(int x) {
T res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
};
int main() {
int n, m;
scanf("%d%d", &n, &m);
BIT<int, 100010> bit;
for (int i = 1; i <= n; i ++) {
int num;
scanf("%d", &num);
bit.add(i, num);
}
while (m --) {
int k, x, y;
scanf("%d%d%d", &k, &x, &y);
if (k == 0) printf("%d\n", bit.query(y) - bit.query(x - 1));
else bit.add(x, y);
}
return 0;
}