线段树

线段树的构成

屏幕快照 2018-12-23 下午2.00.58.png

线段树中每一个节点都是其父节点的左一半或右一半,如果是奇数除不尽的话,中间的那个数归于左一半。并且其中父节点的子子节点编号永远都是父节点的编号的两倍或两倍多1.

每个节点中储存这个节点包含的l-r所有的属性,例如:
如果问区间和,每个节点存l-r区间和
如果问区间最值,每个节点存l-r区间最值

线段树的解题思路

延迟标记

在某一个节点上的延迟标记代表以当前节点为根节点的子树中所有值都是待更改状态(不包括当前节点)。

build函数

可以用build函数一次性初始化线段树也可以用区间修改函数更改线段树。

build函数就是先从树的一号节点递归下去,如果l==r即这个区间只有一个数,将这个数存入树中。回溯的时候将母树的值赋为两个子树的和即

tree[now]=tree[now*2]+tree[now*2+1]

down函数

down函数就是将延迟标记下移的函数。

我们将这个节点的延迟标记赋值给其子节点,并将其子节点的tree更改掉。最后将这个节点的延迟标记删去

change函数

我们区间改值的时候,如果当前区间正好在目标区间的范围内,直接将延迟标记附上去。否则查找左子树和右子树,在查找子树之前
要将延迟标记下放,使子节点的值变为定值,一边最后回溯时的

tree[now]=tree[now*2]+tree[now*2+1];

query函数

当当前区间被所求区间完全包含时直接返回当前点的值即可。否则下放延迟标记后左右继续查询。

易错点梳理

1.在change和query中最开始要下放延迟标记。
2.change中最后要tree[now]=tree[now2]+tree[now2+1]。
3.考虑当当前区间被所求区间包含时的特判。
4.当当前l,r在目标goall,goalr区间内时再搜索。

单点修改,区间查询

这一部分可以用树状数组代替,但是由于树状数组用处太小,所以此处用线段树做。

#include<bits/stdc++.h>
using namespace std;
int x[100005];
int tree[400005];
void build(int l,int r,int now){
    if(l==r){
        tree[now]=x[l];
        return ;
    }
    int mid=(l+r)/2;
    build(l,mid,now<<1);
    build(mid+1,r,now<<1|1);
    tree[now]=tree[now<<1]+tree[now<<1|1];
    return ;
}
void add(int l,int r,int now,int goal,int sum){
    if(l==goal&&r==goal){
        tree[now]+=sum;
        return ;
    }else if(l==r){
        return ;
    }
    int mid=(l+r)/2;
    if(goal<=mid)add(l,mid,now<<1,goal,sum);//这里一定要加一个剪枝
    if(goal>mid)add(mid+1,r,now<<1|1,goal,sum);
    tree[now]=tree[now<<1]+tree[now<<1|1];
    return ;
}
int query(int l,int r,int now,int gl,int gr){
    int ans=0;
    if(l>=gl&&r<=gr){
        return tree[now];
    }
    if(l==r){
        return ans;
    }
    int mid=(l+r)>>1;
    if(gl<=mid)ans+=query(l,mid,now<<1,gl,gr);
    if(gr>mid)ans+=query(mid+1,r,now<<1|1,gl,gr);
    return ans;
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&x[i]);
    }
    build(1,n,1);
    int m;
    cin>>m;
    int op,xx,yy;
    for(int i=0;i<m;i++){
        scanf("%d%d%d",&op,&xx,&yy);
//        cin>>op>>xx>>yy;
        if(op==1){
            add(1,n,1,xx,yy);
        }else{
            printf("%d\n",query(1,n,1,xx,yy));
        }
    }
    return 0;
}

区间修改,区间查询

区间修改时,不要把所有的节点都修改了,要等到查到前再修改,这样可以节省很多时间复杂度。
既然要修改前查,一定要知道修改那些,所以每个节点i用lazy[i]表示这个节点的所有子孙节点应该加上多少(不包括i节点)。

#include<bits/stdc++.h>
using namespace std;
long long a[100005];
long long tree[400005],lazy[400005];
void build(int l,int r,int now){//l,r是当前搜索的区间范围,now是当前节点号
    if(l==r){
        tree[now]=a[l];
        return ;
    }
    int mid=(l+r)/2;
    build(l,mid,now*2);
    build(mid+1,r,now*2+1);
    tree[now]=tree[now*2]+tree[now*2+1];
    return ;
}
void down(int l,int r,int now){//将lazy下放
    if(lazy[now]==0){
        return ;
    }
    int mid=(l+r)/2;
    tree[now*2]+=(mid-l+1)*lazy[now];
    tree[now*2+1]+=(r-mid)*lazy[now]; 
    lazy[now*2]+=lazy[now];
    lazy[now*2+1]+=lazy[now];
    lazy[now]=0;
    return ;
}
void add(int l,int r,int goall,int goalr,int now,long long sum){//goall,goalr是目标范围,sum是要加的数
    if(goall<=l&&r<=goalr){//当前区间在目标区间内时,tree和lazy更新
        tree[now]+=(r-l+1)*sum;//记得是一个区间,所以加的不是一个sum
        lazy[now]+=sum;
        return ;
    }
    if(l==r){
        return ;
    }
    down(l,r,now);
    int mid=(l+r)/2;
    if(goall<=mid)add(l,mid,goall,goalr,now*2,sum);//仅有当下一层区间有一部分被目标区间包括时再向下
    if(mid+1<=goalr)add(mid+1,r,goall,goalr,now*2+1,sum);
    tree[now]=tree[now*2]+tree[now*2+1];
    return ;
}
long long ans;
void query(int l,int r,int goall,int goalr,int now){
    if(goall<=l&&r<=goalr){//当当前区间在目标区间内时,无需继续搜索,答案加上这个数并返回。
        ans+=tree[now];
        return ;
    }
    if(l==r){
        return ;
    }
    down(l,r,now);
    int mid=(l+r)/2;
    if(goall<=mid)query(l,mid,goall,goalr,now*2);
    if(mid+1<=goalr)query(mid+1,r,goall,goalr,now*2+1);
    tree[now]=tree[now*2]+tree[now*2+1];
    return ;
}
int main(){
//    freopen("testdata.in","r",stdin);
//    freopen("t.out","w",stdout);
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    build(1,n,1);
    for(int i=0;i<m;i++){
        long long op,x,y,k;
        scanf("%lld",&op);
        if(op==1){
            scanf("%lld%lld%lld",&x,&y,&k);
            add(1,n,x,y,1,k);
        }else{
            ans=0;
            scanf("%lld%lld",&x,&y);
            query(1,n,x,y,1);
            printf("%lld\n",ans);
        }
    }
    return 0;
}

线段树2(洛谷P3373)

请未完全理解线段树的人勿看
否则。。。你会发现完全懵了,连最简单的线段树都不会了╮(╯▽╰)╭

这道题不仅有查询和区间加法,还有区间乘法。按照普通的线段树的惯例,要用lazy标记表示未完成的区间。
在这里肯定是要分成两个lazy标记分别存放 乘 和 加 。
我这里设为lazy(加),lazyt(乘)。

lazyt表示的是原tree数组未被lazy更新过前乘,lazyt不仅更新lazyt数组,还更新lazy数组
嗯,用几十个字果然无法表达算法的精髓( ̄▽ ̄)"
于是我要将其展开来讲:
$(tree_i*b+c)*d$ 展开来就是 $tree_i*b*d+c*d$ 。tree数组先不看,d不仅更新了原来的乘法lazy,还更新了加法lazy。
在这里由于是tree先乘b*d,所以在更新tree的时候先用lazyt更新,然后再用lazy。
再举几个例子验证一下:
$((tree_i*b)+c+d)*e+f$ 展开得 $tree_i*c*f+d*f+e*f+g$
$(tree_i+b)*c+d$ 展开得 $tree_i*c+b*c+d$
于是就得到

//lazyt更新lazyt
lazyt[now*2]=(lazyt[now*2]*lazyt[now])%p;
lazyt[now*2+1]=(lazyt[now*2+1]*lazyt[now])%p;
//lazyt更新lazy
lazy[now*2]=lazy[now*2]*lazyt[now]%p;
lazy[now*2+1]=lazy[now*2+1]*lazyt[now]%p;
//lazy更新lazy
lazy[now*2]=(lazy[now*2]+lazy[now])%p;
lazy[now*2+1]=(lazy[now*2+1]+lazy[now])%p;
//lazyt先更新tree
tree[now*2]=(tree[now*2]*lazyt[now])%p;
tree[now*2+1]=(tree[now*2+1]*lazyt[now])%p;
//lazy再更新tree
tree[now*2]=(tree[now*2]+lazy[now]*(mid-l+1))%p;
tree[now*2+1]=(tree[now*2+1]+lazy[now]*(r-mid))%p;
//撤销标记
lazy[now]=0;
lazyt[now]=1; 

最后贴代码

#include<bits/stdc++.h>
using namespace std;
long long tree[400005];
long long lazy[400005];
long long lazyt[400005];
long long a[100005];
int n,p;
long long ans;
void down(int l,int r,int now){
    int mid=(l+r)/2;
    tree[now*2]=(tree[now*2]*lazyt[now])%p;
    tree[now*2]=(tree[now*2]+lazy[now]*(mid-l+1))%p;
    tree[now*2+1]=(tree[now*2+1]*lazyt[now])%p;
    tree[now*2+1]=(tree[now*2+1]+lazy[now]*(r-mid))%p;
    
    lazy[now*2]=(lazy[now*2]*lazyt[now])%p;
    lazy[now*2]=(lazy[now*2]+lazy[now])%p;
    lazy[now*2+1]=(lazy[now*2+1]*lazyt[now])%p;
    lazy[now*2+1]=(lazy[now*2+1]+lazy[now])%p;
    
    lazyt[now*2]=(lazyt[now*2]*lazyt[now])%p;
    lazyt[now*2+1]=(lazyt[now*2+1]*lazyt[now])%p;
    
    lazy[now]=0;
    lazyt[now]=1;
}
void build(int l,int r,int now){
    if(l==r){
        tree[now]=a[l]%p;
        return ;
    }
    int mid=(l+r)/2;
    build(l,mid,now*2);
    build(mid+1,r,now*2+1);
    tree[now]=(tree[now*2]+tree[now*2+1])%p;
    return ;
}
void mul(int l,int r,int goall,int goalr,int now,int sum){
    if(l>=goall&&r<=goalr){
        tree[now]=(tree[now]*sum)%p;
        lazyt[now]=(lazyt[now]*sum)%p;
        lazy[now]=(lazy[now]*sum)%p;
        return ;
    }
    down(l,r,now);
    int mid=(l+r)/2;
    if(mid>=goall)mul(l,mid,goall,goalr,now*2,sum);
    if(mid+1<=goalr)mul(mid+1,r,goall,goalr,now*2+1,sum);
    tree[now]=(tree[now*2]+tree[now*2+1])%p;
}
void add(int l,int r,int goall,int goalr,int now,int sum){
    if(l>=goall&&r<=goalr){
        tree[now]=(tree[now]+sum*(r-l+1))%p;
        lazy[now]=(lazy[now]+sum)%p;
        return ;
    }
    down(l,r,now);
    int mid=(l+r)/2;
    if(mid>=goall)add(l,mid,goall,goalr,now*2,sum);
    if(mid+1<=goalr)add(mid+1,r,goall,goalr,now*2+1,sum);
    tree[now]=(tree[now*2]+tree[now*2+1])%p;
}
void query(int l,int r,int goall,int goalr,int now){
    if(l>=goall&&r<=goalr){
        ans+=tree[now];
        ans%=p;
        return ;
    }
    down(l,r,now);
    int mid=(l+r)/2;
    if(mid>=goall)query(l,mid,goall,goalr,now*2);
    if(mid+1<=goalr)query(mid+1,r,goall,goalr,now*2+1);
    tree[now]=(tree[now*2]+tree[now*2+1])%p;
}
int main(){
    for(int i=0;i<400005;i++){
        lazyt[i]=1;
        lazy[i]=0;
    }
    cin>>n>>p;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,n,1);
    int m;
    cin>>m;
    for(int i=0;i<m;i++){
        int op,x,y,z;
        cin>>op;
        if(op==1){
            cin>>x>>y>>z;
            mul(1,n,x,y,1,z);
        }else if(op==2){
            cin>>x>>y>>z;
            add(1,n,x,y,1,z);
        }else if(op==3){
            cin>>x>>y;
            ans=0;
            query(1,n,x,y,1);
            cout<<ans<<endl;
        }
    }
    return 0;
}

本文链接:https://kaispace.com.cn/index.php/archives/113/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者