算法模板(七) 线段树

线段树单点操作

#include<bits/stdc++.h>
using namespace std;
int a[maxn],sumv[maxn*4];
void pushup(int id){
    sumv[id]=sumv[id<<1]+sumv[id<<1 | 1];
}
void build(int id,int l,int r){
    if(l==r){
    sumv[id]=a[l];
    return;
    }
    int mid=(l+r)>>1;
    build(id<<1,l,mid);
    build(id<<1|1,mid+1,r);
}
void update(int id,int l,int r,int x,int v){
    if(l==r){
        sumv[id]+=v;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid)update(id<<1,l,mid,x,v);
    else update(id<<1 | 1,mid+1,r,x,v);
    pushup(id);
}
int query(int id,int l,int r,int x,int y){
    if(x<=l && r<=y)return sumv[id];
    int mid=(l+r)>>1;
    int sum=0;
    if(x<=mid)sum+=query(id<<1,l,mid,x,y);
    if(y>mid)sum+=query(id<<1 | 1,mid+1,r,x,y);
    return sum;
}

线段树区间操作

#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
long long a[maxn],sumv[maxn*4],lazy[maxn*4];
void pushup(long long id){
    sumv[id]=sumv[id<<1]+sumv[id<<1|1];
}
void pushdown(long long id,long long m){
    if(lazy[id]){
        lazy[id<<1]+=lazy[id];
        lazy[id<<1|1]+=lazy[id];
        sumv[id<<1]+=lazy[id]*(m-(m>>1));
        sumv[id<<1|1]+=lazy[id]*(m>>1);
        lazy[id]=0;
    }
}
void build(long long id,long long l,long long r){
    if(l==r){
        sumv[id]=a[l];
        return;
    }
    long long mid=(l+r)>>1;
    build(id<<1,l,mid);
    build(id<<1|1,mid+1,r);
    pushup(id);
}
void update(long long id,long long l,long long r,long long x,long long y,long long v){
    if(x<=l && r<=y){
        sumv[id]+=v*(r-l+1);
        lazy[id]+=v;
        return;
    }
    pushdown(id,r-l+1);
    long long mid=(l+r)>>1;
    if(x<=mid)update(id<<1,l,mid,x,y,v);
    if(y>mid)update(id<<1|1,mid+1,r,x,y,v);
    pushup(id);
}
long long query(long long id,long long l,long long r,long long x,long long y){
    if(x<=l && r<=y)return sumv[id];
    pushdown(id,r-l+1);
    long long mid=(l+r)>>1;
    long long sum=0;
    if(x<=mid)sum+=query(id<<1,l,mid,x,y);
    if(y>mid)sum+=query(id<<1|1,mid+1,r,x,y);
    return sum;
}
long long n,m;
long long u,v,w;
long long cmd;
int main(){
    //freopen("1.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(register long long i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);
    while(m--){
        cin>>cmd;
        if(cmd==1){
            cin>>u>>v>>w;
            update(1,1,n,u,v,w);
        }
        else{
            cin>>u>>v;
            cout<<query(1,1,n,u,v)<<endl;
        }
    }
    return 0;
}