线段树

Author Avatar
Axell 8月 25, 2018
  • 在其它设备中阅读本文章

线段树

线段树,即将点和线段储存在树形结构中,方便查找和修改
需要注意: 线段树很容易出现运行错误,在区间查询和修改时,要注意le必须<=ri

代码实现

变量初始化

int a[MAXN],tree[4*MAXN],add[4*MAXN];  //数组要足够大

建树(build)

void build(int le,int ri,int m){
    if (le==ri){ //不是区间的话直接结束
        tree[m]=a[le];
        return;
    }
    int mid=(le+ri)/2;
    build(le,mid,m*2);
    build(mid+1,ri,m*2+1);
    tree[m]=min(tree[m*2],tree[m*2+1]); //回溯
    // tree[m]=max(tree[m*2],tree[m*2+1]);
    // tree[m]=tree[m*2]+tree[m*2+1];
}

调用参数: build(1,n,1);

获取区间值(get)

获取区间最小值(可以改为区间最大,区间和)

int get(int le,int ri,int nl,int nr,int rt){
       //le,ri:枚举的区间  nl,nr:查找的区间  rt:当前节点
    down(rt,le,ri);
    if (le==nl&&ri==nr) return tree[rt];
    int mid=(le+ri)/2,te;
    if (nr<=mid) te=get(le,mid,nl,nr,rt*2);
    else if (nl>=mid+1) te=get(mid+1,ri,nl,nr,rt*2+1);
    else te=min( get(le,mid,nl,mid,rt*2) , get(mid+1,ri,mid+1,nr,rt*2+1) );
    up(rt,le,ri);
    return te;
}

调用参数: get(1,n,左区间,右区间,1);

更改单点(change)

void change(int le,int ri,int m,int ne,int y){
    if (le==ri) {
        tree[m]=y;
        return;
    }
    int mid=(le+ri)/2;
    if (ne<=mid) change(le,mid,m*2,ne,y);
    if (ne>=mid+1) change(mid+1,ri,m*2+1,ne,y);
    tree[m]=min(tree[m*2],tree[m*2+1]); //回溯
    // tree[m]=max(tree[m*2],tree[m*2+1]);
    // tree[m]=tree[m*2]+tree[m*2+1];
}

调用参数: change(1,n,1,待更改的位置,更改的值);

更改区间值(change)

void change(int le,int ri,int m,int nl,int nr,int y){
    down(m,le,ri);  //见下
    if (le==nl && ri==nr) {
        add[m]+=y;  //懒惰标记
        return;
    }
    int mid=(le+ri)/2;
    if (nr<=mid) change(le,mid,m*2,nl,nr,y);
    else if (nl>=mid+1) change(mid+1,ri,m*2+1,nl,nr,y);
    else change(le,mid,m*2,nl,mid,y) , change(mid+1,ri,m*2+1,mid+1,nr,y);
    up(m,le,ri);   //见下
}

调用参数: change(1,n,1,待更改的位置,更改的值);

懒惰标记的处理

tips

使用懒惰标记后,注意change,get时都要先down,最后up

up
inline void up(int m,int le,int ri){
    int mid=(le+ri)/2;
    tree[m]=tree[m*2]+tree[m*2+1]+add[m*2]*(mid-le+1)+add[m*2+1]*(ri-mid);
}
down
inline void down(int m,int le,int ri){
    tree[m]+=add[m]*(ri-le+1);  //注意这里要*的值
    if (le!=ri){
        add[m*2]+=add[m];
        add[m*2+1]+=add[m];
    }
    add[m]=0;
}

例题

题目描述

罗老师给大家N个数字，用A1, A2, …, AN表示，然后有两个操作：

  1. C a b c： 表示给区间[ Aa, Ab ]， 每个数上增加c的值
  2. Q a b：表示询问区间[ Aa, Ab ]的总和

输入

输入N Q表示N个数和Q个操作

然后输入一行 N个数，表示每个数字初始值

然后输入Q行，每行一个操作，如题目描述的两种操作

输出

对于每个询问操作，输出区间和

样例输入

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

样例输出

4
55
9
15

提示

【数据规模和约定】

1<=N,Q<=100000

-100000000<=Ai<=100000000

-10000<=c<=10000

代码

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

long long a[100005],n,m,y,z;
long long tree[400005],add[400005];
char x;
void build(long long le,long long ri,long long m){
    if (le==ri){
        tree[m]=a[le];
        return ;
    }
    long long mid=(le+ri)/2;
    build(le,mid,m*2);
    build(mid+1,ri,m*2+1);
    tree[m]=tree[m*2]+tree[m*2+1];
}

inline void down(long long m,long long le,long long ri){
    tree[m]+=add[m]*(ri-le+1);  //注意这里要*的值
    if (le!=ri){
        add[m*2]+=add[m];
        add[m*2+1]+=add[m];
    }
    add[m]=0;
}

inline void up(long long m,long long le,long long ri){
    long long mid=(le+ri)/2;
    // long long t=tree[m];
    tree[m]=tree[m*2]+tree[m*2+1]+add[m*2]*(mid-le+1)+add[m*2+1]*(ri-mid);
    // if (t!=tree[m]) cout<<le<<' '<<ri<<' '<<tree[m]<<" up"<<endl;
}

long long get(long long le,long long ri,long long nl,long long nr,long long rt){
    down(rt,le,ri);
    if (le==nl && ri==nr){
        return tree[rt];
    }
    long long mid=(le+ri)/2;
    long long te;
    if (nr<=mid) te=get(le,mid,nl,nr,rt*2);
    else if (nl>=mid+1) te=get(mid+1,ri,nl,nr,rt*2+1);
    else te=get(le,mid,nl,mid,rt*2)+get(mid+1,ri,mid+1,nr,rt*2+1);
    up(rt,le,ri);
    return te;
}

void change(long long le,long long ri,long long m,long long nl,long long nr,long long y){
    down(m,le,ri);
    if (le==nl && ri==nr) {
        add[m]+=y;
        return;
    }
    long long mid=(le+ri)/2;
    if (nr<=mid) change(le,mid,m*2,nl,nr,y);
    else if (nl>=mid+1) change(mid+1,ri,m*2+1,nl,nr,y);
    else change(le,mid,m*2,nl,mid,y) , change(mid+1,ri,m*2+1,mid+1,nr,y);
    up(m,le,ri);
}

int main(){
    cin>>m>>n;
    for (long long i=1;i<=m;++i){
        scanf("%lld",&a[i]);
    }
    build(1,m,1);
    for (long long i=1;i<=n;++i){
        x=getchar();
        while (x!='Q'&&x!='C') x=getchar();
        scanf("%lld %lld",&y,&z);
        if (x=='Q'){
            long long ans;
            ans=get(1,m,y,z,1);
            printf("%lld\n",ans);
        }else{
            long long tmp;
            scanf("%lld",&tmp);
            change(1,m,1,y,z,tmp);
        }
    }
    return 0;
}

知识共享许可协议
本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/38/