POJ 3468 A Simple Problem with Integers（树状数组）

solution：区间更新区间查询的树状数组

#include <iostream>
using namespace std;

long long n,m;
long long a[100005] = {0};
long long sum1[100005];    //(D[1] + D[2] + ... + D[n])
long long sum2[100005];    //(1*D[1] + 2*D[2] + ... + n*D[n])

long long lowbit(long long x){
    return x & (-x);
}

void updata(long long i,long long k){
    long long x = i;    //因为x不变，所以得先保存i值
    while(i <= n){
        sum1[i] += k;
        sum2[i] += k * (x-1);
        i += lowbit(i);
    }
}

long long getsum(long long i){        //求前缀和
    long long res = 0, x = i;
    while(i > 0){
        res += x * sum1[i] - sum2[i];
        i -= lowbit(i);
    }
    return res;
}

int main(){
    cin >> n >> m;
    for(long long i = 1; i <= n; i++){
        cin>>a[i];
        updata(i,a[i] - a[i-1]);   //输入初值的时候，也相当于更新了值
    }
	while (m--)
	{
		char ch;
		long long a, b, c;
		cin >> ch >> a >> b;
		if (ch == 'Q'){
			cout << getsum(b) - getsum(a - 1) << endl;
		}else{
			cin >> c;
			updata(a, c);
			updata(b + 1, -c);
		}
		//[x,y]区间内加上k
	    //updata(x,k);    //A[x] - A[x-1]增加k
	    //updata(y+1,-k);        //A[y+1] - A[y]减少k

	    //求[x,y]区间和
	    //long long sum = getsum(y) - getsum(x-1);
	}
    return 0;
}