简单线段树

模板库

地址
区间加，区间求和

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