[题解]P3372 【模板】线段树 1

yerosius · 2024-12-30 23:44:55 · 题解

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define int ll
int n,q;
struct node{
    ll data,tag;
};
vector<node>tree;
void pushup(int id){
    tree[id].data=tree[id<<1].data+tree[id<<1|1].data;
}
void build(int id,int l,int r){
    if(l==r) cin>>tree[id].data;
    else{
        int mid=l+r>>1;
        build(id<<1,l,mid);
        build(id<<1|1,mid+1,r);
        pushup(id);
    }
}
void addtag(int id,int l,int r,int d){
    tree[id].tag+=d;
    tree[id].data+=(r-l+1)*d;
}
void pushdown(int id,int l,int r){
    if(tree[id].tag){
        int mid=l+r>>1;
        addtag(id<<1,l,mid,tree[id].tag);
        addtag(id<<1|1,mid+1,r,tree[id].tag);
        tree[id].tag=0;
    }
}
int query(int id,int l,int r,int ql,int qr){
    if(l>=ql&&r<=qr) return tree[id].data;//[l,r]属于[ql,qr]
    pushdown(id,l,r);
    ll ans=0,mid=l+r>>1;
    if(ql<=mid) ans+=query(id<<1,l,mid,ql,qr);
    if(qr>mid) ans+=query(id<<1|1,mid+1,r,ql,qr);
    return ans;
}
void modify(int id,int l,int r,int ml,int mr,int d){
    if(l>=ml&&r<=mr) addtag(id,l,r,d);
    else{
        pushdown(id,l,r);
        int mid=l+r>>1;
        if(ml<=mid) modify(id<<1,l,mid,ml,mr,d);
        if(mr>mid) modify(id<<1|1,mid+1,r,ml,mr,d);
        pushup(id);
    }
}
void solve(){
    build(1,1,n);
    while(q--){
        int o;cin>>o;
        switch(o){
            int l,r,k;
            case 1:
            cin>>l>>r>>k;
            modify(1,1,n,l,r,k);
            break;
            case 2:
            cin>>l>>r;
            cout<<query(1,1,n,l,r)<<'\n';
            break;
        }
    }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>q;
    tree.resize(n<<2);
    solve();
    return 0;
}