poj3468 A Simple Problem with Integers---树状数组解法

题目链接：https://vjudge.net/problem/POJ-3468

简单题意：完成区间修改，区间求和的操作

在区间修改，单点求和的模板里，利用差分求出 Ai=Σdj，则A1+...+Ax=ΣΣdj=(x+1)Σdj-Σj*dj，j=1...x，于是用两个树状数组分别维护数组dj和数组j*dj的前缀和即可

#include<cstdio>
#define ll long long
using namespace std;

const int N=1e5+10;
ll n,i,q,c[3][N],a[N];

ll lowbit(ll x){return x&(-x);}
void add(ll x,ll y){
	for (ll i=x;i<=n;i+=lowbit(i)) {
	  c[1][i]+=y; c[2][i]+=x*y; 
	}
}
ll ask(ll x){
	ll res=0;
	for (ll i=x;i>0;i-=lowbit(i)) 
	  res+=((x+1)*c[1][i]-c[2][i]);
	return res;
}

int main(){
	scanf("%lld%lld",&n,&q);
	for (i=1;i<=n;i++){
	  scanf("%lld",&a[i]); add(i,a[i]-a[i-1]); 
	}
	getchar();
	while (q--){
	  char ch; ll l,r,d;
	  scanf("%c",&ch);
	  if (ch=='C'){
	  	scanf("%lld%lld%lld",&l,&r,&d);
	  	add(l,d); add(r+1,-d); 
	  }
	  else {
	  	scanf("%lld%lld",&l,&r);
	    printf("%lld
",ask(r)-ask(l-1)); 
      }
	  getchar();
    }
    return 0;
}