题目链接 :https://cn.vjudge.net/problem/HDU-1166
线段树的基本操作,单点更新,区间查询
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
const int maxn = 1e6 + 5;
#define ll long long
struct node
{
int val;
}e[maxn];
int a[maxn];
void pushup(int cur){
e[cur].val = e[cur<<1].val + e[cur<<1|1].val;
}
void build(int l, int r, int cur) {
if(l == r) {
e[cur].val = a[l];
return ;
}
int m = l + r >> 1;
build(l, m, cur<<1);
build(m + 1, r, cur<<1|1);
pushup(cur);
}
void update(int cl, int cr, int cur, int flag, int pos, int val) {
if(cl == cr) {
e[cur].val += flag * val;
return ;
}
int m = cl + cr >> 1;
if(pos <= m) update(cl, m, cur<<1, flag, pos, val);
else update(m + 1, cr, cur<<1|1, flag, pos, val);
pushup(cur);
}
int query(int cl, int cr, int cur, int l, int r) {
if(l <= cl && cr <= r)
return e[cur].val;
int ans = 0;
int m = cl + cr >> 1;
if(l <= m) ans += query(cl, m, cur<<1, l, r);
if(m < r) ans += query(m + 1, cr, cur<<1|1, l, r);
return ans;
}
int main()
{
int T, t = 1, n, l, r;
scanf("%d",&T);
while(T--) {
scanf("%d",&n);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
build(1, n, 1);
char s[10];
printf("Case %d:\n",t++);
while(~scanf("%s", s)) {
if(s[0] == 'E')break;
scanf("%d%d", &l, &r);
if(s[0] == 'Q') {
printf("%d\n", query(1, n, 1, l, r));
}
else if(s[0] == 'A'){
update(1, n, 1, 1, l, r);
}
else {
update(1, n, 1, -1, l, r);
}
}
}
return 0;
}