ACM线段树模板C++

ACM线段树模板C

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;//数组开大一点
int n,m;
int a[N];
struct node{
    int l,r;//左右端点
    int sum,lazy;//区间和和懒标记
}t[N*4];
void up(int p){//向上更新
    t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}
void down(int p){//向下更新
    if(t[p].lazy){
        t[p<<1].lazy+=t[p].lazy;
        t[p<<1|1].lazy+=t[p].lazy;
        t[p<<1].sum+=t[p].lazy*(t[p<<1].r-t[p<<1].l+1);
        t[p<<1|1].sum+=t[p].lazy*(t[p<<1|1].r-t[p<<1|1].l+1);
        t[p].lazy=0;
    }
}
void build(int p,int l,int r){//建树
    t[p].l=l,t[p].r=r;
    if(l==r){
        t[p].sum=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    up(p);
}
void change(int p,int l,int r,int k){//单点修改
    if(t[p].l==t[p].r){
        t[p].sum=k;
        return;
    }
    down(p);
    int mid=(t[p].l+t[p].r)/2;
    if(r<=mid) change(p<<1,l,r,k);
    else if(l>mid) change(p<<1|1,l,r,k);
    else{
        change(p<<1,l,mid,k);
        change(p<<1|1,mid+1,r,k);
    }
    up(p);
}
void add(int p,int l,int r,int k){//区间修改
    if(t[p].l>=l&&t[p].r<=r){
        t[p].sum+=k*(t[p].r-t[p].l+1);
        t[p].lazy+=k;
        return;
    }
    down(p);
    int mid=(t[p].l+t[p].r)/2;
    if(l<=mid) add(p<<1,l,r,k);
    if(r>mid) add(p<<1|1,l,r,k);
    up(p);
}
int query(int p,int l,int r){//区间查询
    if(t[p].l>=l&&t[p].r<=r) return t[p].sum;
    down(p);
    int mid=(t[p].l+t[p].r)/2,ans=0;
    if(l<=mid) ans+=query(p<<1,l,r);
    if(r>mid) ans+=query(p<<1|1,l,r);
    return ans;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int opt,x,y,k;
        cin>>opt;
        if(opt==1){
            cin>>x>>y>>k;
            add(1,x,y,k);
        }
        if(opt==2){
            cin>>x>>y;
            cout<<query(1,x,y)<<endl;
        }
        if(opt==3){
            cin>>x>>k;
            change(1,x,x,k);
        }
    }
    return 0;
}