A Simple Problem with Integers

http://poj.org/problem?id=3468

http://acm.hdu.edu.cn/showproblem.php?pid=4267

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
//#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,q;
int ans,cnt,flag,temp;
int a[N];
char str[3];
ll lazy[N<<2];
ll tree[N<<2];
void pushup(int rt){
    tree[rt]=tree[rt<<1]+tree[rt<<1|1];
}
void pushdown(int llen,int rlen,int rt){
    tree[rt<<1]+=lazy[rt]*llen;
    tree[rt<<1|1]+=lazy[rt]*rlen;
    lazy[rt<<1]+=lazy[rt];
    lazy[rt<<1|1]+=lazy[rt];
    lazy[rt]=0;
}
void build(int l,int r,int rt){
    if(l==r){
        scanf("%lld",&tree[rt]);
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    pushup(rt);

}
void updata(int l,int r,int rt,int L,int R,int C){
    if(l>=L&&r<=R){
        lazy[rt]+=C;
        tree[rt]+=C*(r-l+1);
        return;
    }
    int mid=(l+r)>>1;
    pushdown(mid-l+1,r-mid,rt);
    if(L<=mid)updata(l,mid,rt<<1,L,R,C);
    if(R>mid)updata(mid+1,r,rt<<1|1,L,R,C);
    pushup(rt);
}
ll query(int l,int r,int rt,int L,int R){
    if(l>=L&&r<=R){
        return tree[rt];
    }
    int mid=(l+r)>>1;
    pushdown(mid-l+1,r-mid,rt);
    ll res=0;
    if(L<=mid)res+=query(l,mid,rt<<1,L,R);
    if(R>mid)res+=query(mid+1,r,rt<<1|1,L,R);
    return res;
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    scanf("%d%d",&n,&q);
    //scanf("%d",&t);
    //while(t--){}
    build(1,n,1);
    int l,r;
    while(q--){
        scanf("%s %d %d",str,&l,&r);
        if(str[0]=='Q')
            cout<<query(1,n,1,l,r)<<endl;
        else{
            scanf("%d",&t);
            updata(1,n,1,l,r,t);
        }


    }

    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

#include <cstdio>

typedef long long LL;

const int maxn =1e5+5;
LL a[2][maxn];
LL psum[maxn];
int n;

inline int lowbit(int x)
{
    return x&-x;
}
void add(LL a[],int x,int d)
{
    while(x<=n)
    {
        a[x]+=d;
        x+=lowbit(x);
    }
}
LL sum(LL a[],int x)
{
    LL ret=0;
    while(x)
    {
        ret+=a[x];
        x-=lowbit(x);
    }
    return ret;
}

LL query(int x)
{
    return sum(a[1],x)*x+sum(a[0],x);
}

int main()
{
    int q;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
    {
        scanf("%I64d",&psum[i]);
        psum[i]+=psum[i-1];
    }
    char op[3];
    while(q--)
    {
        int l,r;
        scanf("%s%d%d",op,&l,&r);
        if(op[0]=='Q')
            printf("%I64d\n",query(r)-query(l-1)+psum[r]-psum[l-1]);
        else
        {
            int c;
            scanf("%d",&c);
            add(a[1],l,c);
            add(a[1],r,-c);
            add(a[0],l,c*(-l+1));
            add(a[0],r,c*r);
        }
    }
}