大佬讲解线段树

https://blog.csdn.net/zearot/article/details/48299459

模板1题目链接

区间修改，区间查询 例题

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
ll sum[N<<2];
int lazy[N<<2];    
ll a[N];
void Getsum(ll pos){
    sum[pos]=sum[pos<<1]+sum[pos<<1|1];
    return ;
}
void PushDown(ll pos,ll lnum,ll rnum){
    if(lazy[pos]){
        lazy[pos<<1]+=lazy[pos];
        lazy[pos<<1|1]+=lazy[pos];
        sum[pos<<1]+=lazy[pos]*lnum;
        sum[pos<<1|1]+=lazy[pos]*rnum;
        lazy[pos]=0;
    }
    return ;
}

void Update(ll L,ll R,ll C,ll l,ll r,ll pos){
    if(l>=L && r<=R){
        sum[pos]+=C*(r-l+1);
        lazy[pos]+=C;
        return ;
    }
    ll m=(l+r)>>1;
    PushDown(pos,m-l+1,r-m);
    if(m>=L) Update(L,R,C,l,m,pos<<1);
    if(m<R)  Update(L,R,C,m+1,r,pos<<1|1);
    Getsum(pos);
}
void Build(ll l,ll r,ll pos){
    if(l==r){
        sum[pos]=a[l];
        return ;
    }
    int m=(l+r)>>1;
    Build(l,m,pos<<1);
    Build(m+1,r,pos<<1|1);
    Getsum(pos);
}
ll Query(ll L,ll R,ll l,ll r,ll pos){
    if(r<=R && l>=L){
        return sum[pos];
    }
    int m=(l+r)>>1;
    PushDown(pos,m-l+1,r-m);
    ll ans=0;

    if(m>=L) ans+=Query(L,R,l,m,pos<<1);
    if(m<R)  ans+=Query(L,R,m+1,r,pos<<1|1);
    return ans;
}

void solve(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    Build(1,n,1);
    for(int i=1;i<=m;i++){
        int op;
        ll x,y,k;
        cin>>op;
        if(op==1){
            cin>>x>>y>>k;
            Update(x,y,k,1,n,1);
        }
        else{
            cin>>x>>y;
            cout<<Query(x,y,1,n,1)<<endl;
        }
    }
}
int main(){
    solve();
}

模板2题目链接

区间查询，单点修改

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10;
int sum[N<<2];
int score[N];
void GetMax(int pos){
    sum[pos]=max(sum[pos<<1],sum[pos<<1|1]);
}
void Build(int l,int r,int pos){
    if(l==r){
        sum[pos]=score[l];
        return ;
    }
    int m=(l+r)>>1;
    Build(l,m,pos<<1);
    Build(m+1,r,pos<<1|1);
    GetMax(pos);
}
void Update(int l,int r,int pos,int id,int grade){    
    if(l==r){
        sum[pos]=grade;
        return ;
    }
    int m=(l+r)>>1;
    if(id<=m) Update(l,m,pos<<1,id,grade);
    else  Update(m+1,r,pos<<1|1,id,grade);
    GetMax(pos);
}
int Query(int L,int R,int l,int r,int pos){
    if(l>=L&&r<=R){
        return sum[pos];
    }
    int m=(l+r)>>1;
    int ans=0;
    if(m>=L) ans=max(ans,Query(L,R,l,m,pos<<1));
    if(m<R)  ans=max(ans,Query(L,R,m+1,r,pos<<1|1));
    return ans;
}
void solve(){
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        for(int i=1;i<=n;i++) scanf("%d",&score[i]);
        Build(1,n,1);
        while(m--){
            char ch;
            int l,r;
            scanf(" %c%d%d",&ch,&l,&r); 
            if(ch=='Q'){
                cout<<Query(l,r,1,n,1)<<endl;
            }
            else{
                Update(1,n,1,l,r);
            }
        }
    }
}
int main(){
    solve();
}

模板3题目链接

区间修改，区间查询 加乘

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
ll add[N<<2],mul[N<<2],ans[N<<2],a[N];
ll mod;
void GetAns(int pos){
    ans[pos]=(ans[pos<<1]+ans[pos<<1|1])%mod;
    return ;
}
void Build(int l,int r,int pos){
    mul[pos]=1;
    add[pos]=0;
    if(l==r){
        ans[pos]=a[l];
        return ;
    }
    int m=(l+r)>>1;
    Build(l,m,pos<<1);
    Build(m+1,r,pos<<1|1);
    GetAns(pos);
}
void PushDown(int pos,int ln,int rn){//下传操作，顾名思义，对pos的子节点进行操作，标记的下传和对ans的影响
    if(add[pos]!=0 || mul[pos]!=1){
        ans[pos<<1]=  (ans[pos<<1]*mul[pos]+add[pos]*ln)%mod; 
        ans[pos<<1|1]=(ans[pos<<1|1]*mul[pos]+add[pos]*rn)%mod;

        add[pos<<1]=  (add[pos]+add[pos<<1]*mul[pos])%mod; 
        add[pos<<1|1]=(add[pos]+add[pos<<1|1]*mul[pos])%mod;

        mul[pos<<1]=  (mul[pos<<1]*mul[pos])%mod;
        mul[pos<<1|1]=(mul[pos<<1|1]*mul[pos])%mod;

        mul[pos]=1;//清除标记 
        add[pos]=0;//同上 
    }
}
void Mul(int L,int R,int k,int l,int r,int pos){
    if(L<=l && r<=R){
        ans[pos]=ans[pos]*k%mod;
        add[pos]=add[pos]*k%mod;
        mul[pos]=mul[pos]*k%mod;
        return ;
    }
    int m=(l+r)>>1;
    PushDown(pos,m-l+1,r-m);
    if(m>=L) Mul(L,R,k,l,m,pos<<1);
    if(m<R)  Mul(L,R,k,m+1,r,pos<<1|1);
    GetAns(pos);//勿忘
    return ;
}
void Add(int L,int R,int c,int l,int r,int pos){
    if(L<=l && r<=R){ 
        ans[pos]=(ans[pos]+c*(r-l+1))%mod;//此位置存在懒标记 
        add[pos]=(add[pos]+c)%mod;
        return ;
    }
    int m=(l+r)>>1;
    PushDown(pos,m-l+1,r-m); 
    if(m>=L) Add(L,R,c,l,m,pos<<1);
    if(m<R)  Add(L,R,c,m+1,r,pos<<1|1);
    GetAns(pos);//勿忘
    return ;
}
ll Query(int L,int R,int l,int r,int pos){
    if(L<=l && r<=R){
        return ans[pos];
    }
    int m=(l+r)>>1;
    PushDown(pos,m-l+1,r-m);//勿忘 
    ll res=0;
    if(m>=L) res=(res+Query(L,R,l,m,pos<<1))%mod;
    if(m<R)  res=(res+Query(L,R,m+1,r,pos<<1|1))%mod;
    return res;
}
void solve(){
    int n,m;
    int op,x,y;
    ll k,c;
    cin>>n>>m>>mod;
    for(int i=1;i<=n;i++) cin>>a[i];
    Build(1,n,1);
    while(m--){
        cin>>op;
        if(op==1){
            cin>>x>>y>>k;
            Mul(x,y,k,1,n,1);
        }
        else if(op==2){
            cin>>x>>y>>c;
            Add(x,y,c,1,n,1);
        }
        else{
            cin>>x>>y;
            cout<<Query(x,y,1,n,1)<<endl;
        }
    }
}
int main(){
    solve();
} 
//核心是PushDown、Add和Mul，理解了规定乘法的优先级大于加法，就能理解这三个函数的代码了

模板1更新（20201102）

对线段树的理解更深了。

//区间查询 单点修改 
#include<bits/stdc++.h>
#define ll long long
const int N=1e5+100;
const int inf=0x3f3f3f3f;
using namespace std;
struct node{
    ll sum,l,r,lazy;
};
node tree[N<<2];
int x,y,n,op,m;
ll a[N],k;
void Build(int i,int l,int r)
{
    tree[i].lazy=0;
    tree[i].l=l;
    tree[i].r=r; 
    if(l==r)
    {
        tree[i].sum=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    Build(i*2,l,mid);
    Build(i*2+1,mid+1,r);
    tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
    return ;
}
void PushDown(int i)
{
    if(!tree[i].lazy) return ;
    tree[2*i].sum+=tree[i].lazy*(tree[2*i].r-tree[2*i].l+1);
    tree[2*i+1].sum+=tree[i].lazy*(tree[2*i+1].r-tree[2*i+1].l+1);

    tree[2*i].lazy+=tree[i].lazy;
    tree[2*i+1].lazy+=tree[i].lazy;
    tree[i].lazy=0;
    return ;
}
void Add(int i,int l,int r,ll c)
{
    if(tree[i].l>=l && tree[i].r<=r)
    {
        tree[i].lazy+=c;
        tree[i].sum+=c*(tree[i].r-tree[i].l+1);
        return ;
    }
    PushDown(i);
    if(tree[2*i].r>=l) Add(2*i,l,r,c);
    if(tree[2*i+1].l<=r) Add(2*i+1,l,r,c);
    tree[i].sum=tree[2*i].sum+tree[2*i+1].sum;
    return ;
}
ll Query(int i,int l,int r)
{
    ll res=0;
    if(tree[i].l>=l && tree[i].r<=r)
    return tree[i].sum;
    if(tree[i].l>r || tree[i].r<l) return 0;
    PushDown(i);
    if(tree[2*i].r>=l) res+=Query(2*i,l,r);
    if(tree[2*i+1].l<=r) res+=Query(2*i+1,l,r);
    return res;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    Build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d%lld",&x,&y,&k);
            Add(1,x,y,k);
        }
        else
        {
            scanf("%d%d",&x,&y);
            printf("%lld\n",Query(1,x,y));
        }
    }
}