萌新刚学线段树，#3WA其余MLE，求调

zhizhi_c @ 2023-01-16 11:55:27

#include<stdio.h>
#define ll long long
ll sumv[200005],add[200005];
int n,m,a[100005],lc[200005],rc[200005],root,np;
inline void pushup(int now){
    sumv[now]=sumv[lc[now]]+sumv[rc[now]];
}

inline void pushdownc(int now,int l,int r,ll d){
    sumv[now]+=(r-l+1)*d;
    add[now]+=d;
}

inline void pushdown(int now,int l,int r){
    int m=(l+r)>>1;
    pushdownc(lc[now],l,m,add[now]);
    pushdownc(rc[now],m+1,r,add[now]);
    add[now]=0;
}

void build(int &now,int l,int r){
    now=++np;
    if(l==r){
        sumv[now]=a[l];
        return;
    }
    int m=(l+r)>>1;
    build(lc[now],l,m);
    build(rc[now],m+1,r);
    pushup(now);
}

void update(int now,int l,int r,int i,int j,ll d){
    if(l>=i && r<=j){
        sumv[now]+=(r-l+1)*d;
        add[now]+=d;
        return;
    }
    pushdown(now,l,r);
    int m=(l+r)>>1;
    if(i<=m) update(lc[now],l,m,i,j,d);
    if(j>m) update(rc[now],m+1,r,i,j,d);
    pushup(now);
}

ll query(int now,int l,int r,int i,int j){
    if(l>=i && r<=j) return sumv[now];
    pushdown(now,l,r);
    ll res=0;
    int m=(l+r)>>1;
    if(i<=m) res+=query(now,l,m,i,j);
    if(r>m) res+=query(now,m+1,r,i,j);
    return res;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",a+i);
    build(root,1,n);
    while(m--){
        int s,x,y;
        scanf("%d%d%d",&s,&x,&y);
        if(s==1){
            int k;
            scanf("%d",&k);
            update(root,1,n,x,y,k);
        }
        else printf("%lld\n",query(root,1,n,x,y));
    }
    return 0;
}

by Ruiqun2009 @ 2023-01-16 11:58:16

@zhizhi_c 你初始化 lc,rc 数组了吗

by zhizhi_c @ 2023-01-16 11:58:24

写错了main函数第2行应为 for(int i=1;i<=n;i++) scanf("%d",a+i);

by zhizhi_c @ 2023-01-16 11:59:40

@Ruiqun2009 初始化了,自动初始化为0

by Ruiqun2009 @ 2023-01-16 12:00:40

@zhizhi_c lc,rc 应该是什么自己想想，不是应该是左儿子和右儿子吗

另外，不用开这两个数组

by Ruiqun2009 @ 2023-01-16 12:04:22

@zhizhi_c

#include<stdio.h>
#define ll long long
ll sumv[200005],add[200005];
int n,m,a[100005],lc[200005],rc[200005],root,np;
inline void pushup(int now){
    sumv[now]=sumv[lc[now]]+sumv[rc[now]];
}

inline void pushdownc(int now,int l,int r,ll d){
    sumv[now]+=(r-l+1)*d;
    add[now]+=d;
}

inline void pushdown(int now,int l,int r){
    int m=(l+r)>>1;
    pushdownc(lc[now],l,m,add[now]);
    pushdownc(rc[now],m+1,r,add[now]);
    add[now]=0;
}

void build(int &now,int l,int r){
    now=++np;
    if(l==r){
        sumv[now]=a[l];
        return;
    }
    int m=(l+r)>>1;
    lc[now]=now*2;
    rc[now]=now*2+1;
    build(lc[now],l,m);
    build(rc[now],m+1,r);
    pushup(now);
}

void update(int now,int l,int r,int i,int j,ll d){
    if(l>=i && r<=j){
        sumv[now]+=(r-l+1)*d;
        add[now]+=d;
        return;
    }
    pushdown(now,l,r);
    int m=(l+r)>>1;
    if(i<=m) update(lc[now],l,m,i,j,d);
    if(j>m) update(rc[now],m+1,r,i,j,d);
    pushup(now);
}

ll query(int now,int l,int r,int i,int j){
    if(l>=i && r<=j) return sumv[now];
    pushdown(now,l,r);
    ll res=0;
    int m=(l+r)>>1;
    if(i<=m) res+=query(lc[now],l,m,i,j);
    if(r>m) res+=query(rc[now],m+1,r,i,j);
    return res;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",a+i);
    root=1;
    build(root,1,n);
    while(m--){
        int s,x,y;
        scanf("%d%d%d",&s,&x,&y);
        if(s==1){
            int k;
            scanf("%d",&k);
            update(root,1,n,x,y,k);
        }
        else printf("%lld\n",query(root,1,n,x,y));
    }
    return 0;
}