题目描述

给定N长的序列，M次操作完成这些。
操作有两种一种是L,R区间内加Z，另一种是询问L,R区间和。

（树状数组）思路

这里使用的是树状数组。
首先对于第一种操作是方便的在树状数组中只需存入A[i]-A[i-1]即可，这样存入进去得出的前缀和则是这个数本身。
例如序列为5的序列分别是 1,2,3,4,5。
这样存入的顺序分别是 1,1,1,1,1。
而求出3的数值则是使用sum函数求出到3位置的前缀和，而3减去一次lowbit(3)=2,2-=lowbit(2)=0。
这里面tr[3]=1,tr[2]=2。
因为1和2一起存入到2里面一次所以tr[2]=2。（复习的时候这里看不懂就去打草稿。）
第二种操作则比较麻烦，因为按照上面这种办法只能求出X这个位置是多少并不能求出区间和。
假设Z(i)=a[i]i。
使用第二个树状数组，里面存储的是Z的值。
这样会trr[]中包含着它在二进制下所有的是1的位置上的Z(i)。
那求出来的办法也简单，则是sm(tr,x)(x+1)-sm(trr,x)。
（具体的推算还是建议在纸上推不然提示到这里都没意义了）

代码

#include<cstdio>
#define ll long long

using namespace std;

const int sz=2e5+1;

char c[2];
int n,m;
ll tr[sz],trr[sz],a[sz];

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

void add(ll tr[],int x,ll y){for(;x<=n;x+=lt(x))tr[x]+=y;}

ll sm(ll tr[],int x)
{
    ll s=0;
    for(;x;x-=lt(x))s+=tr[x];
    return s;
}

ll psm(int x){return sm(tr,x)*(x+1)-sm(trr,x);}

int main()
{
    int i,x,y;ll z;

    scanf("%d%d",&n,&m);
    for(i=1;i<=n;++i)scanf("%lld",a+i),add(tr,i,a[i]-a[i-1]),add(trr,i,(ll)i*(a[i]-a[i-1]));

    while(m--)
    {
        scanf("%s%d%d",c,&x,&y);
        if(c[0]=='Q')printf("%lld\n",psm(y)-psm(x-1));
        else
        {
            scanf("%lld",&z);
            add(tr,x,z);add(trr,x,x*z);
            add(tr,y+1,-z);add(trr,y+1,-z*(y+1));
        }
    }

    return 0;
}

线段树思路（咕）