线段树模板求助

NO_OI_NO_LIFE @ 2023-10-01 20:58:03

#include <bits/stdc++.h> 
#define MAXN 100005
#define ll long long 
using namespace std;

ll n,m,a[MAXN];

struct node{
    ll l,r,tag,add;
}tree[MAXN*4];

void build(ll l,ll r,ll id){
    tree[id].l=l;
    tree[id].r=r;
    if(l==r){
        tree[id].add=a[l];
        return;
    }
    ll mid=l+r>>1;
    build(l,mid,id<<1);
    build(mid+1,r,id<<1||1);
    tree[id].add=tree[id<<1].add+tree[id<<1||1].add;
}

void push_down(ll id){
    tree[id<<1].tag+=tree[id].tag;
    tree[id<<1].add+=(tree[id<<1].r-tree[id<<1].l+1)*tree[id].tag;

    tree[id<<1||1].tag+=tree[id].tag;
    tree[id<<1||1].add+=(tree[id<<1||1].r-tree[id<<1||1].l+1)*tree[id].tag;

    tree[id].tag=0;
}

void update(ll l,ll r,ll id,ll k){
    if(tree[id].l>r||tree[id].r<l) return;
    if(tree[id].l>=l&&tree[id].r<=r){
        tree[id].tag+=k;
        tree[id].add+=(tree[id].r-tree[id].l+1)*k;
        return;
    }
    if(tree[id].tag>0) push_down(id);
    update(l,r,id<<1,k);
    update(l,r,id<<1||1,k);
    tree[id].add=tree[id<<1].add+tree[id<<1||1].add;
}

ll query(ll l,ll r,ll id){
    if(tree[id].l>r||tree[id].r<l) return 0;
    if(tree[id].l>=l&&tree[id].r<=r) return tree[id].add;
    if(tree[id].tag>0) push_down(id);
    return query(l,r,id<<1)+query(l,r,id<<1||1);
}

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

by InversionShadow @ 2023-10-01 21:02:45

|| -> |

by NO_OI_NO_LIFE @ 2023-10-01 21:04:15

@ydq1101 马关且感谢

by _Kingpenguin_ @ 2023-10-01 21:45:37

#include<bits/stdc++.h>
#pragma G++ optimize(2)
using namespace std;

#define int long long
const int N=100005;

int n,m;
int a[N];
struct tree{
    int l,r;
    int val;
    int DelayMark;
}t[4*N];
int opt,u,v,w;

void Build(int p,int l,int r){
    t[p].l=l;
    t[p].r=r;
    if(l==r){
        t[p].val=a[l];
        return;
    }
    int mid=l+r>>1;
    Build(p*2,l,mid);
    Build(p*2+1,mid+1,r);
    t[p].val=t[p*2].val+t[p*2+1].val;
} 

void DelayMarkLowering(int p){
    if(t[p].DelayMark){
        t[p*2].val+=t[p].DelayMark*(t[p*2].r-t[p*2].l+1);
        t[p*2+1].val+=t[p].DelayMark*(t[p*2+1].r-t[p*2+1].l+1);
        t[p*2].DelayMark+=t[p].DelayMark;
        t[p*2+1].DelayMark+=t[p].DelayMark;
        t[p].DelayMark=0;
    }
}

void Change(int p,int u,int v,int w){
    if(u<=t[p].l&&v>=t[p].r){
        t[p].val+=w*(t[p].r-t[p].l+1);
        t[p].DelayMark+=w;
        return;
    }
    DelayMarkLowering(p);
    int mid=t[p].l+t[p].r>>1;
    if(u<=mid) 
        Change(p*2,u,v,w);
    if(v>mid) 
        Change(p*2+1,u,v,w);
    t[p].val=t[p*2].val+t[p*2+1].val;   
}

int Find(int p,int u,int v){
    if(u<=t[p].l&&v>=t[p].r) 
        return t[p].val;
    DelayMarkLowering(p);
    int mid=t[p].l+t[p].r>>1,ans=0;
    if(u<=mid) 
        ans+=Find(p*2,u,v);
    if(v>mid) 
        ans+=Find(p*2+1,u,v);
    return ans;
}

signed main(){
//  freopen("test.in","r",stdin);
//  freopen("test.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    Build(1,1,n);
    while(m--){
        cin>>opt;
        if(opt==1){
            cin>>u>>v>>w;
            Change(1,u,v,w);
        }else{
            cin>>u>>v;
            cout<<Find(1,u,v)<<endl;
        }
    }
    return 0;
}
/*

*/

by _Kingpenguin_ @ 2023-10-01 21:47:06

@2022zhangyuanhao

by NO_OI_NO_LIFE @ 2023-10-03 08:49:29

@IndifferentBreeze 同谢且同学