树状数组的应用（区间修改+区间查询）

树状数组之————区间修改+区间查询

树状数组的工作是 对一组数据进行快速修改查询操作

最基本的功能是 单点修改+区间查询。

然后厉害的是 区间修改+单点查询（用数组del[i]表示原数组a[i]-a[i-1]的值）

更厉害的来了。。。

区间修改+区间查询

用数组del[i]记录原数组a[i]与前一项和，即del[i]=a[i]-a[i-1]

求数组a的前n项和就是：

S(n) = a[1]+a[2]+...a[n]

= del[1] + (del[1]+del[2]) + .... + (del[1]+del[2]+....del[n])

= n*del[1] + (n-1)*del[2] + .... + 1*del[n]

= (n+1 -1)*del[1] + (n+1 -2)*del[2] + .... + (n+1 -n)*del[n]

= (n+1)*(del[1]+del[2]+ ... +del[n]) - (1*del[1] + 2*del[2] + ... + n*del[n])

= (n+1)*sum(del[i], 1<=i<=n) - sum(i*del[i], 1<=i<=n)

其实只需要求出(n+1)*sum(del[i]) ,和 sum(i*del[i], 1<=i<=n)，相减即可

所以就用两个树状数组共同维护

用数组c1[i]维护del[i]

用数组c2[i]维护i*del[i]

对数组进行操作时，用时更新这两个数组即可。查询时，用上面推导的公式

对于那两个查询和修改函数不变，依然沿用最老套的模板

【代码】：

#include<stdio.h>  
#include<iostream>  
using namespace std;  
typedef long long ll;  
ll a[202020];  
ll del[202020];  
ll c1[202020];//维护del  
ll c2[202020];//维护x*del[x]  
ll n;  
void add(ll *c,ll k,ll num)  
{  
    for(;k<=n;k+=k&-k)  
        c[k]+=num;  
}  
ll read(ll *c,ll k)//查询区间1~k  
{  
    ll sum=0;  
    for(;k;k-=k&-k)  
        sum+=c[k];  
    return sum;  
}
ll sum(ll k)
{
	return (k+1)*read(c1,k)-read(c2,k);  
}
int main()  
{  
    cin>>n;  
    for(ll i=1;i<=n;i++){  
        cin>>a[i];  
        del[i]=a[i]-a[i-1];  
        add(c1,i,del[i]);  
        add(c2,i,del[i]*i);  
    }  
    ll Q;cin>>Q;  
    while(Q--)  
    {  
        ll oper;cin>>oper;  
        if(oper==1)  
        {  
            ll a,b,num;  
            cin>>a>>b>>num;  
            add(c1,a,num);  
            add(c1,b+1,-num);  
            add(c2,a,num*a);  
            add(c2,b+1,-num*(b+1));  
        }  
        else  
        {  
            ll a,b;cin>>a>>b;  
            ll sumr=sum(b);  
            ll suml=sum(a-1);
            cout<<sumr-suml<<endl;  
        }  
    }  
}