线段树动态开点（洛谷P13825）

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using i128=__int128;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using db = double;
using ldb = long double;
#define F first
#define S second
#define int ull
const int N=5e6;
struct node{
    int l,r;
    int ls,rs;
    ull sum,tag;
}t[N];
int idx=1;
void addtag(int p,int k){
    t[p].tag+=k;
    t[p].sum+=(t[p].r-t[p].l+1)*k;
}
void push_down(int p){
    if(t[p].tag){
        if(!t[p].ls){
            int l=t[p].l,r=t[p].l+t[p].r>>1;
            t[t[p].ls=++idx]={l,r,0,0,0,0};
        }
        addtag(t[p].ls,t[p].tag);
        if(!t[p].rs){
            int l=(t[p].l+t[p].r>>1)+1,r=t[p].r;
            t[t[p].rs=++idx]={l,r,0,0,0,0};
        }
        addtag(t[p].rs,t[p].tag);
        t[p].tag=0;
    }
}
void push_up(int p){
    t[p].sum=t[t[p].ls].sum+t[t[p].rs].sum;
}
void update(int l,int r,int k,int p){
    if(l<=t[p].l&&t[p].r<=r){
        addtag(p,k);
        return;
    }
    push_down(p);
    int mid=(t[p].l+t[p].r)>>1;
    if(l<=mid){
        if(!t[p].ls){
            int l=t[p].l,r=t[p].l+t[p].r>>1;
            t[t[p].ls=++idx]={l,r,0,0,0,0};
        }
        update(l,r,k,t[p].ls);
    }
    if(mid<r){
        if(!t[p].rs){
            int l=(t[p].l+t[p].r>>1)+1,r=t[p].r;
            t[t[p].rs=++idx]={l,r,0,0,0,0};
        }
        update(l,r,k,t[p].rs);
    }
    push_up(p);
}
ull query(int l,int r,int p){
    if(l<=t[p].l&&t[p].r<=r){
        return t[p].sum;
    }
    push_down(p);
    int mid=(t[p].l+t[p].r)>>1;
    ull ans=0;
    if(l<=mid&&t[p].ls){
        ans+=query(l,r,t[p].ls);
    } 
    if(mid<r&&t[p].rs){
        ans+=query(l,r,t[p].rs); 
    }
    return ans;
}
void solve(){
    int n,m;cin>>n>>m;
    t[1]={1,n,0,0,0,0};
    while(m--){
        int op;cin>>op;
        if(op==1){
            int l,r,k;cin>>l>>r>>k;
            update(l,r,k,1);
        }else{
            int l,r;cin>>l>>r;
            ull ans=(l+r)*(r-l+1)/2+query(l,r,1);
            cout<<ans<<"\n";
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int t=1;
    // cin>>t;
    while(t--) solve();
    return 0;
}