性感线段树板子代码，在线求调

ZM____ML @ 2023-03-21 18:56:54

#include<cstdio>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N=5e6+5;
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+c-48;
        c=getchar();
    }
    return x*f;
}

#define lc (k<<1)
#define rc ((k<<1)|1)
#define mid ((l+r)>>1)

int n,m,tot;
int a[N],sum[N<<4],add[N<<4];
void pushup(int k){
    sum[k]=sum[k<<1]+sum[(k<<1)+1];
}
void pushdown(int k,int l,int r){
    add[k<<1]+=add[k],sum[k<<1]+=add[k]*(mid-lc+1);
    add[(k<<1)|1]+=add[k],sum[(k<<1)|1]+=add[k]*(r-mid);
    add[k]=0;
}
void build(int k,int l,int r){
    if(l==r){
        sum[k]=a[l];
        return;
    }
    build(k<<1,l,mid);
    build((k<<1)|1,mid+1,r);
    pushup(k);
}
void update1(int k,int l,int r,int p,int v){    //a[p]=v
    if(l==r){
        a[l]=v;
        return;
    }
    if(p<=mid) update1(k<<1,l,mid,p,v);
    else update1((k<<1)|1,mid+1,r,p,v);
    pushup(k);
}
void update2(int k,int l,int r,int from,int to,int v){
    if(from<=l&&to>=r){
        add[k]+=v;
        sum[k]+=(r-l+1)*v;
        return;
    }
    pushdown(k,l,r);
    if(from<=mid)update2(k<<1,l,mid,from,to,v);
    if(to>=mid+1)update2((k<<1)|1,mid+1,r,from,to,v);
    pushup(k);
}
int query(int k,int l,int r,int from,int to){   //query[from,to]
    if(from<=l&&to>=r){
        return sum[k];
    }
    int ans=0;
    if(from<=mid)ans+=query(k<<1,l,mid,from,to);
    if(to>=mid+1)ans+=query((k<<1)|1,mid+1,r,from,to);
    return ans;
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int op=read();
        if(op==1){
            int x=read(),y=read(),k=read();
            update2(1,1,n,x,y,k);
        }
        else{
            int x=read(),y=read();
            printf("%d\n",query(1,1,n,x,y));
        }
    }
    return 0;
}

by DengDuck @ 2023-03-21 19:09:33

@ZM____ML 几分

by DengDuck @ 2023-03-21 19:12:27

@ZM____ML 不是，你懒标记为什么不更新sum啊

by Brigid @ 2023-03-21 19:15:33

#include<cstdio>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N=5e6+5;
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+c-48;
        c=getchar();
    }
    return x*f;
}

#define lc (k<<1)
#define rc ((k<<1)|1)
#define mid ((l+r)>>1)

int n,m,tot;
int a[N],sum[N<<4],add[N<<4];
void pushup(int k){
    sum[k]=sum[k<<1]+sum[k<<1 |1];
}
void pushdown(int k,int l,int r){
    add[k<<1]+=add[k],sum[k<<1]+=add[k]*(mid-l+1);
    add[(k<<1)|1]+=add[k],sum[(k<<1)|1]+=add[k]*(r-mid);
    add[k]=0;
}
void build(int k,int l,int r){
    if(l==r){
        sum[k]=a[l];
        return;
    }
    build(k<<1,l,mid);
    build((k<<1)|1,mid+1,r);
    pushup(k);
}
void update2(int k,int l,int r,int from,int to,int v){
    if(from<=l&&to>=r){
        add[k]+=v;
        sum[k]+=(r-l+1)*v;
        return;
    }
    pushdown(k,l,r);
    if(from<=mid)update2(k<<1,l,mid,from,to,v);
    if(to>=mid+1)update2((k<<1)|1,mid+1,r,from,to,v);
    pushup(k);
}
int query(int k,int l,int r,int from,int to){   //query[from,to]
    if(from<=l&&to>=r){
        return sum[k];
    }
    int ans=0;
    pushdown(k, l, r);
    if(from<=mid)ans+=query(k<<1,l,mid,from,to);
    if(to>=mid+1)ans+=query((k<<1)|1,mid+1,r,from,to);
    pushup(k);
    return ans;
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int op=read();
        if(op==1){
            int x=read(),y=read(),k=read();
            update2(1,1,n,x,y,k);
        }
        else{
            int x=read(),y=read();
            printf("%d\n",query(1,1,n,x,y));
        }
    }
    return 0;
}

by __mcx_ @ 2023-03-21 19:20:47

首先这道题区间求和int会溢出要改longlong

其次down函数时左儿子区间长度应是（mid-l+1）而不是（mid-lc+1）lc应为左儿子的区间编号

修改的时候因为完全覆盖的区间直接打了懒标记 在查询的时候会有一部分没有更新到 所以查询每次下放位置时都要更新一次

结合代码理解

#include<cstdio>
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
typedef long long ll;
const int N=5e6+5;
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+c-48;
        c=getchar();
    }
    return x*f;
}

#define lc (k<<1)
#define rc ((k<<1)|1)
#define mid ((l+r)>>1)

int n,m,tot;
int a[N],sum[N<<4],add[N<<4];
void pushup(int k){
    sum[k]=sum[k<<1]+sum[(k<<1)+1];
}
void pushdown(int k,int l,int r){
    add[k<<1]+=add[k],sum[k<<1]+=add[k]*(mid-l+1);
    add[(k<<1)|1]+=add[k],sum[(k<<1)|1]+=add[k]*(r-mid);
    add[k]=0;
}
void build(int k,int l,int r){
    if(l==r){
        sum[k]=a[l];
        return;
    }
    build(k<<1,l,mid);
    build((k<<1)|1,mid+1,r);
    pushup(k);
}
void update1(int k,int l,int r,int p,int v){    //a[p]=v
    if(l==r){
        a[l]=v;
        return;
    }
    if(p<=mid) update1(k<<1,l,mid,p,v);
    else update1((k<<1)|1,mid+1,r,p,v);
    pushup(k);
}
void update2(int k,int l,int r,int from,int to,int v){
    if(from<=l&&to>=r){
        add[k]+=v;
        sum[k]+=(r-l+1)*v;
        return;
    }
    pushdown(k,l,r);
    if(from<=mid)update2(k<<1,l,mid,from,to,v);
    if(to>=mid+1)update2((k<<1)|1,mid+1,r,from,to,v);
    pushup(k);
}
int query(int k,int l,int r,int from,int to){   //query[from,to]
    if(from<=l&&to>=r){
        return sum[k];
    }
    pushdown(k,l,r);
    int ans=0;
    if(from<=mid)ans+=query(k<<1,l,mid,from,to);
    if(to>=mid+1)ans+=query((k<<1)|1,mid+1,r,from,to);
    return ans;
}
signed main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int op=read();
        if(op==1){
            int x=read(),y=read(),k=read();
            update2(1,1,n,x,y,k);
        }
        else{
            int x=read(),y=read();
            printf("%lld\n",query(1,1,n,x,y));
        }
    }
    return 0;
}

by ZM____ML @ 2023-03-21 21:02:32

@DengDuck 谢谢嘎，第一次敲wssb嘎

by ZM____ML @ 2023-03-21 21:02:42

@Brigid 谢谢嘎

by ZM____ML @ 2023-03-21 21:03:06

@_mcx 感谢