以求区间和为例

https://wenku.baidu.com/view/a79fd201f78a6529647d536a.html?from=search

http://blog.csdn.net/zearot/article/details/52280189

http://blog.csdn.net/zearot/article/details/48299459

模板

struct Node
{
    int left,right,val,f;
}node[10010<<2];
int ans;
void build(int l,int r,int id)   //建树
{
    node[id].left=l;
    node[id].right=r;
    node[id].f=0;
    if(l==r)
    {
        scanf("%d",&node[id].val);
        return;
    }
    int m=(l+r)>>1;
    build(l,m,id<<1);
    build(m+1,r,id<<1|1);
    node[id].val=node[id<<1].val+node[id<<1|1].val;
}
void down(int id)
{
    int l1=node[id<<1].left;
    int r1=node[id<<1].right;
    int l2=node[id<<1|1].left;
    int r2=node[id<<1|1].right;
    node[id<<1].f+=node[id].f;
    node[id<<1|1].f+=node[id].f;
    node[id<<1].val+=node[id].f*(r1-l1+1);
    node[id<<1|1].val+=node[id].f*(r2-l2+1);
    node[id].f=0;
}
void update1(int loc,int c,int id)   //单点修改
{
    int l=node[id].left;
    int r=node[id].right;
    if(l==r)
    {
        node[id].val+=c;
        return;
    }
    if(node[id].f)down(id);
    int m=(l+r)>>1;
    if(loc<=m)update1(loc,c,id<<1);
    else update1(loc,c,id<<1|1);
    node[id].val=node[id<<1].val+node[id<<1|1].val;
}
void query1(int loc,int id)   //单点查询
{
    int l=node[id].left;
    int r=node[id].right;
    if(l==r)
    {
        ans=node[id].val;
        return;
    }
    if(node[id].f)down(id);
    int m=(l+r)>>1;
    if(loc<=m)query1(loc,id<<1);
    else query1(loc,id<<1|1);
}
void update2(int L,int R,int c,int id)   //区间修改
{
    int l=node[id].left;
    int r=node[id].right;
    if(l>=L&&r<=R)
    {
        node[id].val+=c*(r-l+1);
        node[id].f+=c;
        return;
    }
    if(node[id].f)down(id);
    int m=(l+r)/2;
    if(L<=m)update2(L,R,c,id<<1);
    if(R>m)update2(L,R,c,(id<<1|1));
    node[id].val=node[id<<1].val+node[id<<1|1].val;
}
void query2(int L,int R,int id)   //区间查询
{
    int l=node[id].left;
    int r=node[id].right;
    if(l>=L&&r<=R)
    {
        ans+=node[id].val;
        return;
    }
    if(node[id].f)down(id);
    int m=(l+r)>>1;
    if(L<=m)query2(L,R,id<<1);
    if(R>m)query2(L,R,(id<<1|1));
}
int main()
{
    int n,q,ope,x,y,z;
    scanf("%d",&n);
    build(1,n,1);
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d",&ope);
        if(ope==1)
        {
            scanf("%d%d",&x,&y);
            update1(x,y,1);
        }
        else if(ope==2)
        {
            scanf("%d",&x);
            query1(x,1);
            printf("%d\n",ans);
        }
        else if(ope==3)
        {
            scanf("%d%d%d",&x,&y,&z);
            update2(x,y,z,1);
        }
        else if(ope==4)
        {
            scanf("%d%d",&x,&y);
            ans=0;
            query2(x,y,1);
            printf("%d\n",ans);
        }
    }
    return 0;
}