索引：
（一）树状数组：
a代表原始数组，c代表树状数组，n很重要！！！！
（1）在多种情况下，树状数组要初始化：void init();
（2）求最低位：int lowbit(int x);
（3）单点更新：void update(int x,int y);
（4）前x项求和：int getsum(int x);

（二）线段树
a代表原始数组，segtree代表线段树结构体
（1）建线段树，相当于初始化：void build(int l,int r,int rt);
（2）单点更新：void update(int L,int C,int l,int r,int rt);
（3）区间求和：int query(int L,int R,int l,int r,int rt);
（4）下推   ：void pushdown(int rt,int ln,int rn);  //用于区间更新
（5）区间更新：void qujian_update(int L,int R,int C,int l,int r,int rt);
（6）区间更新的区间查询：void qujian_update(int L,int R,int C,int l,int r,int rt);
树状数组:
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stdlib.h>
using namespace std;
typedef long long ll;

int a[50005]; //原数组
int c[50005]; //树状数组

void init() //初始化a,c数组
{
    memset(a, 0, sizeof(a));
    memset(c, 0, sizeof(c));
}

int n; //一共多少个兵营

int lowbit(int x)
{
    return x&(-x);
}

void updata(int i,int k) //在i位置加上k，并更新数组的数据
{
    while(i<=n) 
    {
        c[i]+=k;
        i+=lowbit(i);
    }
}

int getsum(int i) //求前i项的和
{
    int ans=0;
    while(i>0)
    {
        ans+=c[i];
        i-=lowbit(i);
    }
    return ans;
}



线段树：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
using namespace std;
const int maxn = 50005;
int T,n;
int a[maxn];
string s;
struct sss
{
    int val,lazy;
}SegTree[maxn<<2];

void build(int l,int r,int rt)
{
    SegTree[rt].lazy = 0;
    if(l==r)
    {
        SegTree[rt].val = a[l];
        return;
    }
    int mid = (l+r)/2;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    SegTree[rt].val = SegTree[rt<<1].val + SegTree[rt<<1|1].val; //回溯方法
}

void update(int L,int C,int l,int r,int rt)
{
    if(l==r)
    {
        SegTree[rt].val += C;  //这里是rt的val+=C,不是l或r的
        return;
    }
    int mid = (l+r) >> 1 ;
    if(L <= mid) update(L, C, l, mid, rt<<1);
    else         update(L, C, mid+1, r, rt<<1|1);
    SegTree[rt].val = SegTree[rt<<1].val + SegTree[rt<<1|1].val;
}


void pushdown(int rt,int ln,int rn)
{
    if(SegTree[rt].lazy)
    {
        SegTree[rt<<1].lazy += SegTree[rt].lazy;
        SegTree[rt<<1|1].lazy += SegTree[rt].lazy;
        SegTree[rt<<1].val += SegTree[rt].lazy * ln;
        SegTree[rt<<1|1].val += SegTree[rt].lazy *rn;
        SegTree[rt].lazy = 0;
    }
}
void qujian_update(int L,int R,int C,int l,int r,int rt)
{
    if(l>=L && r<=R) //只有[l,r]全部在[L,R]区间内才可以更新，直到是叶子节点
    {
        SegTree[rt].val += C * (r-l+1);
        SegTree[rt].lazy += C;
        return;
    }
    int mid = (l+r) >> 1;
    pushdown(rt,mid-l+1,r-mid);
    if(L<=mid) qujian_update(L, R, C, l, mid, rt<<1);
    if(R>mid)  qujian_update(L, R, C, mid+1 ,r, rt<<1|1);
    SegTree[rt].val = SegTree[rt<<1].val + SegTree[rt<<1|1].val;
}

int query(int L,int R,int l,int r,int rt)
{
    if(l>=L && r<=R) return SegTree[rt].val;
    if(l>R || r<L) return 0;
    int mid = (l+r)>>1;
    return query(L, R, l, mid, rt<<1) + query(L, R, mid+1, r, rt<<1|1);
}

int qujian_query(int L,int R,int l,int r,int rt)
{
    if(l>=L && r<=R) return SegTree[rt].val;
    if(l>R || r<L) return 0;
    int mid = (l+r)>>1;
    pushdown(rt, mid-l+1, r-mid);
    return qujian_query(L, R, l, mid, rt<<1) + qujian_query(L, R, mid+1, r, rt<<1|1);
}

int main()
{
    scanf("%d",&T);
    for (int I=1;I<=T;I++)
    {
        cout << "Case " << I << ":" << endl;
        scanf("%d",&n);
        for (int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        build(1, n, 1); //相当于初始化，不用像树状数组单独初始化了
        while(cin >> s)
        {
            int x,y;
            if(s=="End") break;
            else
            {
                scanf("%d %d",&x,&y);
                if(s=="Add") update(x, y, 1, n, 1);
                if(s=="Sub") update(x, -y, 1, n, 1);
                if(s=="Query") cout << query(x, y, 1, n, 1) << endl;
            }
        }
    }
    return 0;
}