POJ 3468 A Simple Problem with Integers(线段树 成段增减+区间求和)

A Simple Problem with Integers

【题目链接】A Simple Problem with Integers

【题目类型】线段树 成段增减+区间求和

&题解：

线段树 成段增减+区间求和 模板题 这种题真的应该理解并且可以流畅的独立码出来了

【时间复杂度】\(O(nlogn)\)

&代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
#define cle(a,val) memset(a,(val),sizeof(a))
#define SI(N) scanf("%d",&(N))
#define SII(N,M) scanf("%d %d",&(N),&(M))
#define SIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define red(i,a,b) for(int i=(a);i>=(b);i--)
const ll LINF = 0x3f3f3f3f3f3f3f3f;
#define PU(x) cout<<#x<<endl;
#define PI(A) cout<<(A)<<endl;
#define DG(x) cout<<#x<<"="<<(x)<<endl;
#define DGG(x,y) cout<<#x<<"="<<(x)<<" "<<#y<<"="<<(y)<<endl;
#define DGGG(x,y,z) cout<<#x<<"="<<(x)<<" "<<#y<<"="<<(y)<<" "<<#z<<"="<<(z)<<endl;
#define PIar(a,n) rep(i,0,n-1)cout<<a[i]<<" ";PU()
#define PIarr(a,n,m) rep(aa,0,n-1){rep(bb,0,m-1)cout<<a[aa][bb]<<" ";PU()}
typedef pair<int, int> pii;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
const double EPS = 1e-9 ;
/*     C o d i n g  S p a c e     */

#define lsn b,m,rt<<1
#define rsn m+1,e,rt<<1|1

const int maxn = (int)1e5 + 9 ;
int n,q,a[maxn];
ll seg[maxn<<2],si[maxn<<2];
void puup(int rt) {
    seg[rt]=seg[rt<<1]+seg[rt<<1|1];
}
void pudo(int len,int rt) {
    if(si[rt]) {
        si[rt<<1]+=si[rt];
        si[rt<<1|1]+=si[rt];
        seg[rt<<1]+=si[rt]*(len-len/2);
        seg[rt<<1|1]+=si[rt]*(len/2);
        si[rt]=0;
    }
}
void build(int b,int e,int rt) {
    if(b==e) {
        seg[rt]=a[b];
        return ;
    }
    int m=b+e>>1;
    build(lsn);
    build(rsn);
    puup(rt);
}
ll query(int l,int r,int b,int e,int rt) {
    if (l<=b&&e<=r) {
        return seg[rt];
    }
    pudo(e-b+1,rt);
    int m=b+e>>1;
    ll ans=0;
    //小于等于m的全在左儿子  大于m的全在右儿子
    //如果需要求的区间[l,r]最左边的那个(也就是l) 小于等于m 那么就一定要往左儿子走
    //反之 如果区间[l,r]最右边的那个(也就是r) 大于m 那么就一定要走向右儿子
    if (l<=m)
        ans+=query(l,r,lsn);
    if (m<r)
        ans+=query(l,r,rsn);
    return ans;
}
void upda(int l,int r,ll xx,int b,int e,int rt) {
    if (l<=b&&e<=r) {
        si[rt]+=xx;
        seg[rt]+=(e-b+1)*xx;
        return;
    }
    pudo(e-b+1,rt);
    int m=b+e>>1;
    if (l<=m)
        upda(l,r,xx,lsn);
    if (m<r)
        upda(l,r,xx,rsn);
    puup(rt);
}
void Solve() {
    scanf("%d%d",&n,&q);
    rep(i,1,n) scanf("%d",&a[i]);
    build(1,n,1);
    rep(o,1,q) {
        char op[9];
        int x,y,z;
        scanf("%s",op);
        if (op[0]=='Q') {
            scanf("%d%d",&x,&y);
            printf("%lld\n",query(x,y,1,n,1));
        }
        else {
            scanf("%d%d%d",&x,&y,&z);
            upda(x,y,z,1,n,1);
        }
    }
}
int main() {
//iostream::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    // int T;cin>>T;while(T--)
    Solve();
    return 0;
}