给定长度为N的数列A,然后输入M行操作指令。
第一类指令形如“C l r d”,表示把数列中第l~r个数都加d。
第二类指令形如“Q X”,表示询问数列中第x个数的值。
对于每个询问,输出一个整数表示答案。
输入格式
第一行包含两个整数N和M。
第二行包含N个整数A[i]。
接下来M行表示M条指令,每条指令的格式如题目描述所示。
输出格式
对于每个询问,输出一个整数表示答案。
每个答案占一行。
数据范围
1≤N,M≤1051≤N,M≤105,
|d|≤10000|d|≤10000,
|A[i]|≤1000000000|A[i]|≤1000000000
输入样例:
10 5
1 2 3 4 5 6 7 8 9 10
Q 4
Q 1
Q 2
C 1 6 3
Q 2
输出样例:
4
1
2
5
题解:利用树状数组来记录每次改变的值,如果修改[l, r]之间的值,增加val,则令[l, n]加上val,[r + 1, n]减去val,然后查询值得时候,就是用树状数组得查询,然后加上原来数组里面得值就是答案。
#include <iostream>
#include <cstdio> using namespace std; typedef long long ll; const int maxn = 1e5+; ll arr[maxn];
ll tree[maxn];
int n, m; int lowbit(int x) {
return x & (-x);
} void add(int x, ll val) {
while(x <= n) {
tree[x] += val;
x += lowbit(x);
}
} ll ask(int x) {
ll res = ;
while(x >= ) {
res += tree[x];
x -= lowbit(x);
}
return res;
} int main() {
scanf("%d %d", &n, &m);
for(int i = ; i <= n; i++) {
scanf("%lld", &arr[i]);
}
while(m--) {
char str[];
int l, r;
ll val;
scanf("%s", str);
if(str[] == 'Q') {
scanf("%d", &l);
printf("%lld\n", ask(l) + arr[l]);
} else {
scanf("%d%d%lld", &l, &r, &val);
add(l, val); //在[l, n]的区间内增加val
add(r + , -val); //在[r + 1, n]的区间内减少val
}
}
return ;
}