线段树

· · 算法·理论

例题引入

P3372 【模板】线段树 1

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
long long n,m;
long long a[N];
long long tree[N*4];
long long tag[N*4];
long long ls(int p){
    return p<<1;
}
long long rs(long long p){
    return p<<1|1;
}
void push_up(long long p){
    tree[p]=tree[ls(p)]+tree[rs(p)];
}
void build (long long p,long long l,long long r){
    tag[p]=0;
    if(l==r){
        tree[p]=a[l];
        return ;
    }
    long long mid=(l+r)/2;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    push_up(p);
}
void addtage(long long p,long long l,long long r,long long d){
    tag[p]+=d;
    tree[p]+=(r-l+1)*d;
}
void push_down(long long p,long long l,long long r){
    if(tag[p]){
        long long mid=(l+r)>>1;
        addtage(ls(p),l,mid,tag[p]);
        addtage(rs(p),mid+1,r,tag[p]);
        tag[p]=0;
    }
}

void update(long long p,long long L,long long R,long long pl,long long pr,long long d){
    if(L<=pl&&R>=pr){
        addtage(p,pl,pr,d);
        return ; 
    }
    push_down(p,pl,pr);
    long long mid=(pl+pr)>>1;

    if(L<=mid)update(ls(p),L,R,pl,mid,d);
    if(R>mid)update(rs(p),L,R,mid+1,pr,d);
    push_up(p);
}
long long chaxun(long long p,long long L,long long R,long long pl,long long pr){
    if(L<=pl&&R>=pr)return tree[p];
    push_down(p,pl,pr);
    long long ans=0;
    long long mid=(pl+pr)>>1;
    if(L<=mid)ans+=chaxun(ls(p),L,R,pl,mid);
    if(R>mid)ans+=chaxun(rs(p),L,R,mid+1,pr);
    return ans;
}
int main(){
    cin>>n>>m;
    for(long long i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    for(long long i=1;i<=m;i++){
        long long q;long long x,y,k;
        cin>>q;
        if(q==1){
            cin>>x>>y>>k;
            update(1,x,y,1,n,k);
        }
        else{
            cin>>x>>y;
            cout<<chaxun(1,x,y,1,n)<<endl;
        } 
    }
    return 0;
}

总结

改每个节点的值

void push_up(long long p){
    tree[p]=tree[ls(p)]+tree[rs(p)];
}

建树

void build (long long p,long long l,long long r){
    tag[p]=0;
    if(l==r){
        tree[p]=a[l];
        return ;
    }
    long long mid=(l+r)/2;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    push_up(p);
}

区间改值

void update(long long p,long long L,long long R,long long pl,long long pr,long long d){
    if(L<=pl&&R>=pr){
        addtage(p,pl,pr,d);
        return ; 
    }
    push_down(p,pl,pr);
    long long mid=(pl+pr)>>1;
    if(L<=mid)update(ls(p),L,R,pl,mid,d);
    if(R>mid)update(rs(p),L,R,mid+1,pr,d);
    push_up(p);
}

查询区间

long long chaxun(long long p,long long L,long long R,long long pl,long long pr){
    if(L<=pl&&R>=pr)return tree[p];
    push_down(p,pl,pr);
    long long ans=0;
    long long mid=(pl+pr)>>1;
    if(L<=mid)ans+=chaxun(ls(p),L,R,pl,mid);
    if(R>mid)ans+=chaxun(rs(p),L,R,mid+1,pr);
    return ans;
}