【题解】Luogu P3372 【【模板】线段树 1】

这里就是区间修改和查询区间和的线段树,与POJ 3468重题。

#include<cstdio>

typedef long long int64;

const int MAXN = 100000 + 6;

int a[MAXN];

class SegmentTree{
    public:int l,r;
    public:int64 sum,add;
};
SegmentTree t[MAXN * 4];

inline int LEFT(int x){return x << 1;}
inline int RIGHT(int x){return x << 1 | 1;}
inline int MID(int l,int r){return (l + r) >> 1;}

void build(int p,int l,int r){
    t[p].l = l;t[p].r = r;
    if(l == r){
        t[p].sum = a[l];
        return;
    }
    build(LEFT(p),l,MID(l,r));
    build(RIGHT(p),MID(l,r) + 1,r);
    t[p].sum = t[LEFT(p)].sum + t[RIGHT(p)].sum;
}

void spread(int p){
    if(t[p].add){
        t[LEFT(p)].sum += (t[p].add * (t[LEFT(p)].r - t[LEFT(p)].l + 1));
        t[RIGHT(p)].sum += (t[p].add * (t[RIGHT(p)].r - t[RIGHT(p)].l + 1));
        t[LEFT(p)].add += t[p].add;
        t[RIGHT(p)].add += t[p].add;
        t[p].add = 0;
    }
}

void change(int p,int l,int r,int d){
    if(l <= t[p].l && r >= t[p].r){
        t[p].sum += ((int64)d * (t[p].r - t[p].l + 1));
        t[p].add += d;
        return;
    }
    spread(p);
    if(l <= MID(t[p].l,t[p].r)){
        change(LEFT(p),l,r,d);
    }
    if(r > MID(t[p].l,t[p].r)){
        change(RIGHT(p),l,r,d);
    }
    t[p].sum = t[LEFT(p)].sum + t[RIGHT(p)].sum;
}

int64 ask(int p,int l,int r){
    if(l <= t[p].l && r >= t[p].r){
        return t[p].sum;
    }
    spread(p);
    int64 ans = 0;
    if(l <= MID(t[p].l,t[p].r)){
        ans += ask(LEFT(p),l,r);
    }
    if(r > MID(t[p].l,t[p].r)){
        ans += ask(RIGHT(p),l,r);
    }
    return ans;
}

int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    
    for(int i = 1;i <= n;i++){
        scanf("%d",&a[i]);
    }
    build(1,1,n);
    while(m--){
        int op,x,y,k;
        scanf("%d",&op);
        if(op == 1){
            scanf("%d %d %d",&x,&y,&k);
            change(1,x,y,k);
        }else{
            scanf("%d %d",&x,&y);
            printf("%lld\n",ask(1,x,y));
        }
    }
    
    return 0;
}