一个简单的整数问题2

树状数组的第三种用法,区间修改,区间查询.
仔细讲下.假设我们要求a[l-r]里面的和,而我们知道a[l]=d[1-l].

用代码表示a[l~r]的和就是：
int sum=0;
for(int i=l;i<=r;i++)
{
    for(int j=1;j<=i;j++)
    {
        sum+=a[j];
    }
}
()表示对1到n求和
n*a[1]+(n-1)*a[2]+...+a[n]=n*()*d[i]-()(d[i]*(i-1)).

我们要这样想树状数组的功能是对1到n求和.
代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+5;
ll a[N],d[N],sum1[N],sum2[N],n;
ll lowbit(ll x)
{
    return x&(-x);
}

void insert(ll pos,ll val)
{
    ll x=pos;
    while(pos<=n)
    {
        sum1[pos]+=val;
        sum2[pos]+=val*(x-1);
        pos+=lowbit(pos);
    }
}

ll query(ll pos)
{
    ll res=0;
    ll x=pos;
    while(pos>0)
    {
        res+=(x*sum1[pos]-sum2[pos]);
        pos-=lowbit(pos);
    }
    return res;
}

int main()
{
    ll m;
    scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    for(ll i=1;i<=n;i++)
    {
        insert(i,a[i]-a[i-1]);
    }
    while(m--)
    {
        string s;
        ll l,r,x;
        cin>>s;
        if(s=="Q")
        {
            cin>>l>>r;
            cout<<query(r)-query(l-1)<<endl;
        }
        else
        {
            cin>>l>>r>>x;
            insert(l,x);
            insert(r+1,-x);
        }
    }
    return 0;
}