线段树模板

线段树

就是个模板

orz几乎一遍写不对

#include<cstdio>
#include<algorithm>
#include<cstring>
#define MAXN 100009
#define LL long long
LL a[MAXN];
LL n,m;
class Segment_Tree{
    private:
        LL cnt;
        struct T{
            LL ls,rs,left_range,right_range,sum,lazy;
        };
        T tree[MAXN<<1];
        LL seglen(LL x){
            return tree[x].right_range-tree[x].left_range+1;
        }
        void update(LL x){
            tree[x].sum=tree[tree[x].ls].sum+tree[tree[x].rs].sum;
        }
        void pushdown(LL x){
            if(tree[x].lazy){
                if(tree[x].ls){
                    tree[tree[x].ls].lazy+=tree[x].lazy;
                    tree[tree[x].ls].sum+=tree[x].lazy*seglen(tree[x].ls);
                }
                if(tree[x].rs){
                    tree[tree[x].rs].lazy+=tree[x].lazy;
                    tree[tree[x].rs].sum+=tree[x].lazy*seglen(tree[x].rs);
                }
            }
            tree[x].lazy=0;
        }
    public:
        LL Build(LL l,LL r){
            LL now=++cnt;
            tree[now].left_range=l;tree[now].right_range=r;
            if(l==r){
                tree[now].sum=a[l];
                return now;
            }
            LL mid=(l+r)>>1;
            tree[now].ls=Build(l,mid);
            tree[now].rs=Build(mid+1,r);
            update(now);
            return now;
        }
        void addnum(LL now,const LL &l,const LL &r,const LL &v){
            pushdown(now);
            if(l<=tree[now].left_range && tree[now].right_range<=r){
                tree[now].sum+=v*seglen(now);
                tree[now].lazy+=v;
                return;
            }
            LL mid=(tree[now].left_range+tree[now].right_range)>>1;
            if(l<=mid) addnum(tree[now].ls,l,r,v);
            if(r>=mid+1) addnum(tree[now].rs,l,r,v);
            update(now);
        }
        LL r2n(LL now,const LL &l,const LL &r){
            pushdown(now);
            if(l<=tree[now].left_range && tree[now].right_range<=r){
                return tree[now].sum;
            }
            LL mid=(tree[now].left_range+tree[now].right_range)>>1;
            LL re=0;
            if(l<=mid) re+=r2n(tree[now].ls,l,r);
            if(r>=mid+1) re+=r2n(tree[now].rs,l,r);
            update(now);
            return re;
        }
}Seg;
int main(){
    scanf("%lld%lld",&n,&m);
    LL i;
    for(i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    Seg.Build(1,n);
    for(i=1;i<=m;i++){
        LL opt,l,r,x;
        scanf("%lld%lld%lld",&opt,&l,&r);
        if(opt==1){
            scanf("%lld",&x);
            Seg.addnum(1,l,r,x);
        }
        else
            printf("%lld\n",Seg.r2n(1,l,r));
    }
    return 0;
}