线段树0分求调

lmn985 @ 2024-11-18 21:35:47

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int d[N],tp[N];
int n,m,a[N],o,x,y,z;
void build(int l,int r,int p){
    if(l==r)d[p]=a[l];
    else{
        int mid=(l+r)/2;
        build(l,mid,p*2);
        build(mid+1,r,p*2+1);
        d[p]=d[p*2]+d[p*2+1];
    }
}
void pushdown(int s,int t,int p){
    if(tp[p]!=0){
        int mid=(s+t)/2;
        d[p*2]+=tp[p]*(mid-s+1);
        d[p*2+1]+=tp[p]*(t-mid);
        tp[p*2]+=tp[p];
        tp[p*2+1]+=tp[p];
        tp[p]=0;
    }
}
void update(int l,int r,int s,int t,int c,int p){
    if(l<=s and t<=r){
        d[p]+=c*(t-s+1);
        tp[p]+=c;
        return ;
    }
    pushdown(s,t,p);
    int mid=(s+t)/2;
    if(l<=mid)update(l,r,s,mid,c,p*2);
    if(r>mid)update(l,r,mid+1,t,c,p*2+1);
}
int getsum(int l,int r,int s,int t,int p){
    if(l<=s and t<=r)return d[p];
    pushdown(s,t,p);
    int mid=(s+t)/2,sum=0;
    if(l<=mid)sum+=getsum(l,r,s,mid,p*2);
    if(r>mid)sum+=getsum(l,r,mid+1,t,p*2+1);
    return sum;
}
signed main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>a[i];
    build(0,n-1,1);
    while(m--){
        cin>>o;
        if(o==1){
            cin>>x>>y>>z;
            x--,y--;
            update(x,y,0,n-1,z,1);
        }
        else{
            cin>>x>>y;
            x--,y--;
            cout<<getsum(x,y,0,n-1,1)<<"\n";
        }
    }
}

by lmn985 @ 2024-11-18 21:37:06

悬赏关注

by HKW0202 @ 2024-11-18 21:42:52

加法操作完没有update@lmn985

by Ff472130 @ 2024-11-18 21:43:06

@lmn985

update函数最后要push_up

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int d[N],tp[N];
int n,m,a[N],o,x,y,z;
void build(int l,int r,int p){
    if(l==r)d[p]=a[l];
    else{
        int mid=(l+r)/2;
        build(l,mid,p*2);
        build(mid+1,r,p*2+1);
        d[p]=d[p*2]+d[p*2+1];
    }
}
void pushdown(int s,int t,int p){
    if(tp[p]!=0){
        int mid=(s+t)/2;
        d[p*2]+=tp[p]*(mid-s+1);
        d[p*2+1]+=tp[p]*(t-mid);
        tp[p*2]+=tp[p];
        tp[p*2+1]+=tp[p];
        tp[p]=0;
    }
}
void update(int l,int r,int s,int t,int c,int p){
    if(l<=s and t<=r){
        d[p]+=c*(t-s+1);
        tp[p]+=c;
        return ;
    }
    pushdown(s,t,p);
    int mid=(s+t)/2;
    if(l<=mid)update(l,r,s,mid,c,p*2);
    if(r>mid)update(l,r,mid+1,t,c,p*2+1);
    d[p]=d[p*2]+d[p*2+1];//加这一句 
}
int getsum(int l,int r,int s,int t,int p){
    if(l<=s and t<=r)return d[p];
    pushdown(s,t,p);
    int mid=(s+t)/2,sum=0;
    if(l<=mid)sum+=getsum(l,r,s,mid,p*2);
    if(r>mid)sum+=getsum(l,r,mid+1,t,p*2+1);
    return sum;
}
signed main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>a[i];
    build(0,n-1,1);
    while(m--){
        cin>>o;
        if(o==1){
            cin>>x>>y>>z;
            x--,y--;
            update(x,y,0,n-1,z,1);
        }
        else{
            cin>>x>>y;
            x--,y--;
            cout<<getsum(x,y,0,n-1,1)<<"\n";
        }
    }
}

by imzfx_Square @ 2024-11-18 21:43:58

@lmn985 update 最后一行要加 pushup（即 d[p]=d[p*2]+d[p*2+1]）

by HKW0202 @ 2024-11-18 21:45:04

啊说错了，没有pushup

d[p]=d[p*2]+d[p*2+1];

by lmn985 @ 2024-11-18 22:00:21

谢谢各位大佬，AC了。