线段树

模板

视频讲的是维护最大值,这里的模板是求和的

模板(区间求和)

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

vector<ll>tree,lazy;

void init(int n){tree.assign(4*n+5,0);lazy.assign(4*n+5,0);}

void pull(int id){tree[id]=tree[id<<1]+tree[id<<1|1];}

void apply(int id,int l,int r,ll v){tree[id]+=v*(r-l+1);lazy[id]+=v;}

void push(int id,int l,int r){
    if(lazy[id]==0)return;
    int m=(l+r)>>1;
    apply(id<<1,l,m,lazy[id]);
    apply(id<<1|1,m+1,r,lazy[id]);
    lazy[id]=0;
}

void build(int id,int l,int r,const vector<ll>&a){
    if(l==r){tree[id]=a[l];return;}
    int m=(l+r)>>1;
    build(id<<1,l,m,a);
    build(id<<1|1,m+1,r,a);
    pull(id);
}

void add(int id,int l,int r,int L,int R,ll v){
    if(L<=l&&r<=R){apply(id,l,r,v);return;}
    push(id,l,r);
    int m=(l+r)>>1;
    if(L<=m)add(id<<1,l,m,L,R,v);
    if(R>m)add(id<<1|1,m+1,r,L,R,v);
    pull(id);
}

ll sumq(int id,int l,int r,int L,int R){
    if(L<=l&&r<=R)return tree[id];
    push(id,l,r);
    int m=(l+r)>>1;ll s=0;
    if(L<=m)s+=sumq(id<<1,l,m,L,R);
    if(R>m)s+=sumq(id<<1|1,m+1,r,L,R);
    return s;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;
    vector<ll>a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    init(n);
    build(1,1,n,a);
    int q;cin>>q;
    while(q--){
        int op;cin>>op;
        if(op==1){
            int L,R;ll v;cin>>L>>R>>v;
            add(1,1,n,L,R,v);
        }else{
            int L,R;cin>>L>>R;
            cout<<sumq(1,1,n,L,R)<<"\n";
        }
    }
}

这里我做了一个网页实现了可视化,链接线段树-1755576145367.html

当然觉得我可视化做的不行的也可以看另一个网站的

https://visualgo.net/zh/segmenttree