树状数组或线段树都可以
树状数组写法
#include<cstdio> #include<algorithm> #include<iostream> #include<cmath> #include<queue> #include<vector> #include<cstring> using namespace std; typedef long long ll; int const MAXN = 50010; int c[MAXN * 4],a[MAXN * 4]; int n; int Lowit(int x){ return x & (-x); } int Add(int x,int d){ while(x <= n){ c[x] += d; x += Lowit(x); } } int Sum(int x){ int ret = 0; while(x > 0){ ret += c[x]; x -= Lowit(x); } return ret; } int main(){ int t; while(~scanf("%d",&t)){ for(int k = 1;k <= t;k++){ memset(c,0,sizeof(c)); memset(a,0,sizeof(a)); scanf("%d",&n); for(int i = 1;i <= n;i++){ scanf("%d",&a[i]); Add(i,a[i]); } printf("Case %d:\n",k); while(1){ char str[10]; scanf("%s",str); int aa,bb;; if(str[0] == 'A' || str[0] == 'S'){ scanf("%d%d",&aa,&bb); if(str[0] == 'S') bb = -bb; a[aa] += bb; Add(aa,bb); } else if(str[0] == 'Q'){ scanf("%d%d",&aa,&bb); printf("%d\n",Sum(bb) - Sum(aa - 1)); } else break; } } } return 0; } /* 1 10 1 2 3 4 5 6 7 8 9 10 Query 1 3 Add 3 6 Query 2 7 Sub 10 2 Add 6 3 Query 3 10 End */