线段树：

1 #include
     
       2 #include
      
        3 using namespace std; 4 int sum; 5 int s1[100000],s2[1000000]; 6 int build(int l,int r,int p) 7 { 8    if (l==r) return s2[p]=s1[l]; 9    int m=(l+r)/2;10    int a=build(l,m,2*p);11    int b=build(m+1,r,2*p+1);12    return s2[p]=a+b;13 }14 void un(int l,int r,int p,int pos,int c)15 {16     if (l<=pos&&r>=pos) s2[p]+=c;17     if (l==r) return ;18     int m=(l+r)/2;19     if (pos<=m) un(l,m,2*p,pos,c);20     else un(m+1,r,2*p+1,pos,c);21     return ;22 }23 void find(int l,int r,int p,int ll,int rr)24 {25     if (ll<=l&&rr>=r) {sum+=s2[p];return ;}26     if (ll>r||rr
      
     

 

树状数组：

 

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5  6 const int mx = 100005; 7 int a[mx]; 8 int n; 9 10 int lowbit(int x)11 {12     return x&-x;13 }14 15 void updata(int i,int x)16 {17     if (i>n) return ;18     a[i]+=x;19     i+=lowbit(i);20     updata(i,x);21 }22 23 int sum(int i)24 {25     if (i<=0) return 0;26     return a[i]+sum(i-lowbit(i));27 }28 29 int main()30 {31    int t;32    scanf("%d",&t);33    for (int cas=1;cas<=t;cas++)34    {35        printf("Case %d:\n",cas);36        scanf("%d",&n);37        memset(a,0,sizeof(a));38        for (int i=1;i<=n;i++)39        {40            int b;41            scanf("%d",&b);42            updata(i,b);43        }44        char s[10];45        while(1)46        {47            int u,v;48            scanf("%s",s);49            if (s[0]=='E') break;50            scanf("%d%d",&u,&v);51            if (s[0]=='Q') printf("%d\n",sum(v)-sum(u-1));52            if (s[0]=='A') updata(u,v);53            if (s[0]=='S') updata(u,-v);54        }55    }56 }