基础树状数组,但我是用线段树解决这个问题的,线段树相对麻烦,但是单纯为了应用一下,毕竟学到这了
#include<iostream> #include<cstdio> #include<cstring> #include<map> using namespace std; #define maxn 50005 #define lson p<<1 #define rson p<<1|1 struct NODE { int l,r,sum; } node[maxn<<4]; void build(int l,int r,int p) { node[p].l = l,node[p].r = r; if(l == r) { int num; scanf("%d",&num); node[p].sum = num; return; } int mid = (l+r) >> 1; build(l,mid,lson); build(mid+1,r,rson); node[p].sum = node[lson].sum + node[rson].sum ; } int ask(int l,int r,int p) { if(node[p].l == l && node[p].r == r) { return node[p].sum; } int mid = (node[p].l + node[p].r) >> 1; if(r <= mid) return ask(l,r,lson); else if(l >= mid+1) return ask(l,r,rson); else return ask(l,mid,lson) + ask(mid+1,r,rson); } void update(int num,int p,int op) { if(node[p].l==node[p].r && node[p].l == num) { node[p].sum += op; return; } int mid = (node[p].l + node[p].r) >> 1; if(num <= mid) update(num,lson,op); else if(num >= mid+1) update(num,rson,op); else { update(num,lson,op); update(num,rson,op); } node[p].sum = node[lson].sum + node[rson].sum; } int main() { int t; scanf("%d",&t); int tot = 0; while(t--) { int n; printf("Case %d: ",++tot); scanf("%d",&n); build(1,n,1); char op[20]; while(~scanf("%s",op) && op[0] != 'E') if(op[0] == 'Q') { int l,r; scanf("%d%d",&l,&r); printf("%d ",ask(l,r,1)); } else if(op[0] == 'A') { int num,opn; scanf("%d%d",&num,&opn); update(num,1,opn); } else { int num,opn; scanf("%d%d",&num,&opn); update(num,1,-opn); } } return 0; }