树状数组（三）【区间修改，区间查询】

【区间修改，区间查询】
同样利用到了差分数组。
求区间和可以是求两个前缀和再相减，比如求l~r的和，可以是s( r)-s(l-1)，所以问题就是求前缀和。

原数组为a，他的差分数组为x，(a1=x1=0)
则a1=x1，a2=x1+x2，… ，an=x1+x2+…+xn
那么前缀和
s(n)=a1+a2+…+an
=(x1)+(x1+x2)+…+(x1+x2+…+xn)
=n(x1+x2+…+xn)-(0* x1+1* x2+…+(n-1)* xn)
所以维护x1, x2, … ,xn和 (0)*x1, (1)*x2, … (n-1)*xn这两个数组就好了。

区间修改
差分数组怎么修改，这个就怎么修改，两个数组同时改。
区间查询
求两个和再相减就好了。

洛谷模板题：线段树1
其实是线段树的模板题，但可以用树状数组来做，要比线段树好写，还快

#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i=a;i<b;i++)
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int MXN = 1e5+5;
//a是原数组,x是a的差分数组,t1是x1~xn的树状数组,t2是0*x1~(n-1)*xn的树状数组
ll a[MXN],x[MXN],t1[MXN],t2[MXN];
int n,m;
void build()//建树状数组
{
    rep(i,1,n+1){
        t1[i]+=x[i];
        t2[i]+=(i-1)*x[i];
        int j=i+lowbit(i);
        if(j<=n) t1[j]+=t1[i],t2[j]+=t2[i];
    }
}
void update(int l,int r,ll x)//区间修改，l~r变化x
{
    int i=l;
    while(i<=n){
        t1[i]+=x;
        t2[i]+=(l-1)*x;
        i+=lowbit(i);
    }
    i=r+1;
    while(i<=n){
        t1[i]-=x;
        t2[i]-=r*x;
        i+=lowbit(i);
    }
}
ll getsum(int k)//求前缀和
{
    ll sum=0;int i=k;
    while(i>0){
        sum+=k*t1[i];
        sum-=t2[i];
        i-=lowbit(i);
    }
    return sum;
}
int main()
{
    scanf("%d %d",&n,&m);
    rep(i,1,n+1) scanf("%lld",&a[i]);
    rep(i,1,n+1) x[i]=a[i]-a[i-1];
    build();
    int p,l,r;
    ll x;
    rep(i,0,m){
        scanf("%d",&p);
        if(p==1){
            scanf("%d %d %lld",&l,&r,&x);
            update(l,r,x);
        }
        else{
            scanf("%d %d",&l,&r);
            printf("%lld\n",getsum(r)-getsum(l-1));
        }
    }
    return 0;
}

上面那次提交是树状数组，下面那个是之前写的线段树，对于这道题，树状数组还是很快的。