线段树

线段树的构成

屏幕快照 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.考虑当当前区间被所求区间包含时的特判。

区间修改,区间查询

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

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
long long n,m;
long long tree[2000020],lazy[2000020];//lazy标记用于以后的整个区间都加一的时候
using namespace std;
void down(long long p,long long l, long long r){
    long long mid=(l+r)/2;
    if(lazy[p]==0){//如果没有标上lazy标记,直接通过
        return ;
    }else{//将其子节点标上,并把其子节点增加,把自己的lazy消掉
        tree[p*2]+=(mid-l+1)*lazy[p];
        tree[p*2+1]+=(r-mid)*lazy[p];
        lazy[p*2]+=lazy[p];
        lazy[p*2+1]+=lazy[p];
        lazy[p]=0;
    }
}
//把p节点区间[l,r]中的[x,y]增加z
void modify(long long p,long long l,long long r,long long x,long long y,long long z){
    //如果整个区间都是完全属于查询区域的话做懒惰标记(lazy[])
    if(x<=l&&r<=y){
        tree[p]+=(r-l+1)*z;//将自己先加上所有叶子节点所加的数
        lazy[p]+=z;
        return ;
    }else{
        //计算区间划分
        down(p,l,r);//先将刚才的父节点的子节点全都加上一定的数,并且把lazy标记消掉,然后把子节点表上lazy标记,因为后面还有需要加的
        long long mid=(l+r)/2;
        //左
        if(x<=mid){
            modify(p*2,l,mid,x,y,z);
        }
        //右
        if(y>=mid+1){
            modify(p*2+1,mid+1,r,x,y,z);
        }
        //修改好子树之后更新当前节点
        tree[p]=tree[p*2]+tree[p*2+1];
    }
}

//在p节点的区间[l,r]种,查询[x,y]的区间和
long long query(long long p,long long l,long long r,long long x,long long y){
    //当前区域完全属于所要查询的区域,直接返回
    if(x<=l&&r<=y){
        return tree[p];
    }
    //左右区间划分
    down(p,l,r);
    long long res=0;
    long long mid=(l+r)/2;
    //左
    if(x<=mid){
        res+=query(p*2,l,mid,x,y);//如果左边有,就继续查找其左节点
    }
    //右
    if(y>=mid+1){
        res+=query(p*2+1,mid+1,r,x,y);
    }
    return res;
}
int main() {
    cin>>n>>m;
    memset(tree,0,sizeof(tree));
    memset(lazy,0,sizeof(lazy));
    for(long long i=1;i<=n;i++){
        long long tmp;
        cin>>tmp;
        modify(1,1,n,i,i,tmp);//初始化整棵树,第一个1是要从跟节点往下,1代表跟节点编号,第二个1以及第三个n是表示节点所包括的范围,i,i,tmp即为需要增加的区间(也可以说是节点)以及增加的数量tmp
    }
    for(long long i=1;i<=m;i++){
        long long type,x,y;
        cin>>type>>x>>y;
        if(type==1){//区间修改
            long long z;
            cin>>z;
            modify(1,1,n,x,y,z);//第一个1是要从根节点往下,1代表根节点。第二个1和第三个n是表示节点所包括的范围,x,y,z即为需要增加的区间以及增加的数目。
        }else{
            cout<<query(1,1,n,x,y)<<endl;//第一个1是要从根节点往下,1代表根节点。第二个1和第三个n是表示节点所包括的范围,x,y即为需要查询的范围。
        }
        
    }
    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],lazy[400005],lazyt[400005];
long long n,m,p;
long long tmp;
void down(long long now,long long l,long long r){
    long long mid=(l+r)/2;
    lazyt[now*2]=(lazyt[now*2]*lazyt[now])%p;
    lazyt[now*2+1]=(lazyt[now*2+1]*lazyt[now])%p;
    lazy[now*2]=lazy[now*2]*lazyt[now]%p;
    lazy[now*2+1]=lazy[now*2+1]*lazyt[now]%p;
    lazy[now*2]=(lazy[now*2]+lazy[now])%p;
    lazy[now*2+1]=(lazy[now*2+1]+lazy[now])%p;
    tree[now*2]=(tree[now*2]*lazyt[now])%p;
    tree[now*2+1]=(tree[now*2+1]*lazyt[now])%p;
    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; 
}
void build(long long now,long long l,long long r){
    long long mid=(l+r)/2;
    if(l==r){
        scanf("%lld",&tmp);
        tree[now]=tmp;
        return ;
    }
    build(now*2,l,mid);
    build(now*2+1,mid+1,r);
    tree[now]=tree[now*2]+tree[now*2+1];
    return ;
}
void add(long long now,long long l,long long r,long long dl,long long dr,long long sum){
//    prlong longf("now:%lld\tl:%lld\tr:%lld\tdl:%lld\tdr:%lld\n",now,l,r,dl,dr);
    long long mid=(l+r)/2;
    if(l==dl&&r==dr){
        tree[now]=(tree[now]+sum*(r-l+1)%p)%p;
        lazy[now]=(lazy[now]+sum)%p;
        return ;
    }
    down(now,l,r);
    if(dl<=mid)add(now*2,l,mid,dl,min(mid,dr),sum);
    if(dr>mid)add(now*2+1,mid+1,r,max(mid+1,dl),dr,sum);
    tree[now]=(tree[now*2]+tree[now*2+1])%p;
    return ;
}
long long ans;
void query(long long now,long long l,long long r,long long dl,long long dr){
    
    long long mid=(l+r)/2;
    if(l==dl&&r==dr){
        ans=(ans+tree[now])%p;
        return ;
    }
    down(now,l,r);
    if(dl<=mid)query(now*2,l,mid,dl,min(mid,dr));
    if(dr>mid)query(now*2+1,mid+1,r,max(mid+1,dl),dr);
    tree[now]=(tree[now*2]+tree[now*2+1])%p;
    return ;
}
void times(long long now,long long l,long long r,long long dl,long long dr,long long sum){
    long long mid=(l+r)/2;
    if(l==dl&&r==dr){
        tree[now]=(tree[now]*sum)%p;
        lazyt[now]=(lazyt[now]*sum)%p;
        lazy[now]=(lazy[now]*sum)%p;
        return ;
    }
    down(now,l,r);
    if(dl<=mid)times(now*2,l,mid,dl,min(mid,dr),sum);
    if(dr>mid)times(now*2+1,mid+1,r,max(mid+1,dl),dr,sum);
    tree[now]=(tree[now*2]+tree[now*2+1])%p;
    return ;
}
int main(){
    for(long long i=0;i<400005;i++){
        lazy[i]=0;
        lazyt[i]=1;
    }
    scanf("%lld%lld%lld",&n,&m,&p);
    build(1,1,n);
    long long sel,x,y,k;
    for(long long i=0;i<m;i++){
        scanf("%lld",&sel);
        if(sel==1){
            scanf("%lld%lld%lld",&x,&y,&k);
            times(1,1,n,x,y,k);
        }else if(sel==2){
            scanf("%lld%lld%lld",&x,&y,&k);
            add(1,1,n,x,y,k);
        }else if(sel==3){
            ans=0;
            scanf("%lld%lld",&x,&y);
            query(1,1,n,x,y);
            printf("%lld\n",ans%p);
        }
    }
    return 0;
} 

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

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