线段树2

ZhouM
2025-12-20 20:05:21
发布于：广东
4阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define ll long long
ll tree[4*N];
ll lazy[4*N];
#define pl(x) (x*2)
#define pr(x) ((x*2)+1)

void lazy_down(ll p,ll l,ll r){//将节点p上的懒标记下传
    if(!lazy[p])return ;

    ll mid=(l+r)>>1;
    tree[pl(p)]+=lazy[p]*((mid-l)+1);//左子节点管理区间[l,mid]
    lazy[pl(p)]+=lazy[p];

    tree[pr(p)]+=lazy[p]*(r-(mid+1)+1);//右节点管理区间[mid+1,r];
    lazy[pr(p)]+=lazy[p];
    
    lazy[p]=0;//重置lazy
}

//p:节点编号,[ul,ur]进行修改的区间,[l,r]就是节点p管理的区间
//区间[ul,ur]的值全都加上val
void update(ll p,ll ul,ll ur,ll val,ll l,ll r){
    if(ur<l||r<ul)return ;//保险,防止修改区间和管理区间不重合

    if(ul<=l&&r<=ur){
        //[mxl,mir]就是修改区间和管理区间的重合部分
        tree[p]+=val*(r-l+1);//计算结果
        lazy[p]+=val;
        return ;
    }
    lazy_down(p,l,r);
    
    ll mid=(l+r)>>1;
    
    update(pl(p),ul,ur,val,l,mid);
    update(pr(p),ul,ur,val,mid+1,r);

    tree[p]=tree[pl(p)]+tree[pr(p)];
}
//查询区间[ql,qr]的和
ll query(ll p,ll ql,ll qr,ll l,ll r){
    if(qr<l||r<ql)return 0;//保险,防止修改区间和管理区间不重合
    //管理区间包含查询区间
    if(ql<=l&&r<=qr){
        return tree[p];
    }
    lazy_down(p,l,r);
    ll mid=(l+r)>>1;
    ll res=0;
    res+=query(pl(p),ql,qr,l,mid);
    res+=query(pr(p),ql,qr,mid+1,r);
    return res;
}


void solve(){
    ll n,m;
    cin>>n>>m;
    for(ll i=1;i<=n;i++){
        ll x;cin>>x;
        update(1,i,i,x,1,N-1);
    }
    while(m--){
        ll op;cin>>op;
        if(op==1){
            ll l,r,k;
            cin>>l>>r>>k;
            update(1,l,r,k,1,N-1);//修改区间的值
        }else if(op==2){
            ll l,r;
            cin>>l>>r;
            cout<<query(1,l,r,1,N-1)<<endl;
        }
    }
}
int main(){
    ll t=1;
    // cin>>t;
    while(t--){
        solve();
    }
}
有帮助，赞一个
去预览
0/2000
这里空空如也
热门讨论
