线段树模板全RE求调

记录

#include<iostream>
using namespace std;
using ll=long long;
const int N=1e5+2;
struct segment_tree{
    ll w,tag;
    segment_tree():w(0),tag(0) {}
}t[N*4];
ll n,m,a[N];
void maketag(ll u,ll len,ll x) {
    t[u].tag+=x;
    t[u].w+=len*x;
}
void pushup(ll u) {
    t[u].w=t[u*2].w+t[u*2+1].w;
}
void pushdown(ll u,ll l,ll r) {
    ll mid=(l+r)/2;
    maketag(u*2,mid-l+1,t[u].tag);
    maketag(u*2+1,r-mid,t[u].tag);
    t[u].tag=0;
}
void build(ll u,ll l,ll r) {
    if(l==r) {
        t[u].w=a[l];
        return;
    }
    ll mid=(l+r)/2;
    build(u*2,l,mid);
    build(u*2+1,mid+1,r);
    pushup(u);
}
bool in(ll _l,ll _r,ll l,ll r) {
    return l<=_l&&_r<=r;
}
bool out(ll _l,ll _r,ll l,ll r) {
    return r<_l||_r<l;
}
ll query(ll u,ll _l,ll _r,ll l,ll r) {
    if(in(_l,_r,l,r)) return t[u].w;
    if(!out(_l,_r,l,r)) {
        ll mid=(l+r)/2;
        pushdown(u,_l,_r);
        return query(u*2,_l,mid,l,r)+query(u*2+1,mid+1,_r,l,r);
    }
    return 0;
}
void update(ll u,ll _l,ll _r,ll l,ll r,ll x) {
    if(in(_l,_r,l,r)) maketag(u,_r-_l+1,x);
    else if(!out(_l,_r,l,r)) {
        ll mid=(l+r)/2;
        pushdown(u,_l,_r);
        update(u*2,_l,mid,l,r,x);
        update(u*2+1,mid+1,_r,l,r,x);
        pushup(u);
    }
}
int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    ll op,x,y,k;
    cin>>n>>m;
    for(int i=1;i<=n;++i) cin>>a[i];
    build(1,1,n);
    while(m--) {
        cin>>op>>x>>y;
        if(op==1) {
            cin>>k;
            update(1,1,n,x,y,k);
        }
        else cout<<query(1,1,n,x,y)<<'\n';
    }
    return 0;
}