poj A Simple Problem with Integers 改段求段 树状数组

题目链接：A Simple Problem with Integers

题解：这题应该是线段树，但用两个树状数组bit1[i]表示原来位置上的值，bit2[i]表示前i个元素都要加bit2[i]的值，对与这个数组的前缀和等与get_sum(bit1,i)+get_sum(bit2,i)**i，所以当我们要对L,R.区间都加上c时。
值要只要对bit2[L]加上c,这样会对前面的L-1个数多加了个c，然后我们在bit1[L]减去c(L-1).然后因为R以后的都不要加所以在bit2[R+1]加上-c,这样前面的一段L，R就都没加值的所以还要在
bit1[R+1]的位置加上（R-L+1）c;

//#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<algorithm>
#define pb push_back
#define ll long long
#define PI 3.14159265
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#define eps 1e-7
using namespace std;
const int maxn=1e5+5;
int n,q;
ll bit1[maxn],bit2[maxn];
ll lowbit(int x)
{
    return x&(-x);
}
void add(ll *b,ll x,ll y)
{
    for(int i=x;i<=n;i+=lowbit(i))
    {
        b[i]+=y;
    }
}
ll get_sum(ll *b,int x)
{
    ll ans=0;
    for(int i=x;i>0;i-=lowbit(i))
    {
        ans+=b[i];
    }
    return ans;
}
int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++)
    {
        int a;
        cin>>a;
        add(bit1,i,a);
    }
    while(q--)
    {
        string op;
        cin>>op;
        if(op=="Q")
        {
            ll l,r;
            cin>>l>>r;
            ll ans=get_sum(bit1,r)+get_sum(bit2,r)*r;
            ans-=get_sum(bit1,l-1)+get_sum(bit2,l-1)*(l-1);
            cout<<ans<<'
';
        }
        else
        {
            ll l,r,c;
            cin>>l>>r>>c;
            add(bit1,l,-c*(l-1));
            add(bit2,l,c);
            add(bit1,r+1,c*r);
            add(bit2,r+1,-c);
        }

    }
	return 0;
 }