POJ - 3468 A Simple Problem with Integers（树状数组，区间修改，区间查询）

POJ - 3468 A Simple Problem with Integers

线段树写法

树状数组写法

#include<cstdio>
typedef long long ll;
const int N = 1e5+10;
ll sum1[N],sum2[N];//树状数组
int a[N];//原数组 
int n,m;
int lowbit(int x){
    return (x&-x);}
void add(ll x,ll y)
{
    for(int i=x;i<=n;i+=lowbit(i)){
    sum1[i]+=y;sum2[i]+=x*y;}
}
ll getsum(int x)
{
    ll res=0;for(int i=x;i;i-=lowbit(i)) res+=(x+1)*sum1[i]-sum2[i];return res;
}
int main()
{
    scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){
    scanf("%d",&a[i]);add(i,a[i]-a[i-1]);}int l,r,k;char op;while(m--){
    scanf(" %c",&op);if(op=='C'){
    scanf("%d%d%d",&l,&r,&k);add(l,k);add(r+1,-k);}if(op=='Q'){
    scanf("%d%d",&l,&r);printf("%lld\n",getsum(r)-getsum(l-1));}}return 0;
}