极简版线段树

2018-09-10 00:58:39来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

作者作为一个蒟蒻,也是最近才自学了线段树,不对的地方欢迎大佬们评论,但是不要喷谢谢

好啦,我们就开始说说线段树吧

线段树是个支持区间操作和查询的东东,平时的话还是蛮实用的

下面以最基本的区间加以及查询区间和为例

线段树顾名思义就是棵树嘛,叶子节点是每个基本点,它们所对应的父亲就是它们的和,具体如下图

3,4,5都是基本点

但是对于这样的线段树来说,操作所需的时间是远达不到我们的要求的(会被t),因为我们会进行一些不必要的操作,就像如果没有查询到某个点,那么就没有必要去修改这个点的值,为此,我们会引入一个懒标记,记录每个基本点需要被加上的值(称为add),那么树上任意一个点需要增加的值=该点对应的区间长度*add

那么总的来说,线段树的基本操作我个人认为可以分成3个,建树、修改和查询,当然如果继续细分也是口以(可以)的,就比如说还可以分出 区间和的向上传递(父亲节点等于子节点的和)和懒标记的向下传递(子节点的懒标记=原来的懒标记+父节点的懒标记)

所以接下来我们就来看看建树、修改和查询这3部分的具体代码吧(深呼吸)

首先是建树(build)

#define ls 2*rt,l,(l+r)/2                //left son
#define rs 2*rt+1,(l+r)/2+1,r      //right son
#define ll long long
void build(ll rt,ll l,ll r)//rt是当前点,l和r代表l到r区间的和
{
    if(r==l)
//也就是说,我们找到了一个叶子节点,自己到自己的和 就是自己嘛
    {
        scanf("%lld",&su[rt]);//那我们就输入这个节点的值
    }
    else//否则就去看看当前点的左右儿子
    {
        build(ls);//看左儿子
        build(rs);//看右儿子
        //当rt的左右儿子都准备好了,我们就可以求出rt的值了
        su[rt]=su[2*rt]+su[2*rt+1];
    }
    return;
} //一层一层的求,我们就可以建好一个初步的树啦

然后是修改(change)

#define ls 2*rt,l,(l+r)/2          //左右儿子,和之前一样
#define rs 2*rt+1,(l+r)/2+1,r
#define ll long long
void change(ll rt,ll l,ll r,ll L,ll R,ll add)
//当前点,当前区间的左右端点,需要修改的区间的左右端点,需要给每个基本点加上的值
{
    if(l>=L&&r<=R)//如果说当前区间是需要修改区间的子集
    {
        su[rt]+=add*(r-l+1);
        //那么就修改当前点,注意乘上当前区间长度
        o[rt]+=add;
//记得修改懒标记 return;//别忘了返回! } if(o[rt]!=0) //如果说我们恰好经过了一个被打上懒标记的点,那不如就顺手把它的懒标记下传好了 { //修改左右儿子的值 su[rt*2]+=o[rt]*((r+l)/2-l+1);// (r+l)/2是区间中点 su[rt*2+1]+=o[rt]*(r-(r+l)/2);//实际应乘以(r-((r+l)/2+1)+1)但+1-1抵消了 o[rt*2]+=o[rt]; o[rt*2+1]+=o[rt]; //下传懒标记注意是加上父节点的懒标记不是等于 o[rt]=0;//清除懒标记 } if(L<=(l+r)/2) //二分思想,如果需要修改的区间左端点在当前区间中点的左边,即当前区间中点左侧有需要修改的点的话 { change(ls,L,R,add);//那就去修改啊 } if(R>(l+r)/2)//同理 { change(rs,L,R,add); } su[rt]=su[2*rt]+su[2*rt+1];//橘氏春秋有云(什么鬼)有下就有上,改完记得上传 return; }

呼啊,已经完成2/3了,坚持就是胜利!↖(^ω^)↗

查询(find)

void find(ll rt,ll l,ll r,ll L,ll R)
//当前点,当前区间左右端点,需要查询的区间左右端点
{
    if(l>=L&&r<=R)//如果当前区间是查询区间的子集
    {
        ans[c]+=su[rt];//答案就加上当前点的值
    }
    else//不然就找找它应该在那个区间里面
    {
        if(o[rt]!=0)//顺便下传rt的懒标记
        {
            su[rt*2]+=o[rt]*((r+l)/2-l+1);
            su[rt*2+1]+=o[rt]*(r-(r+l)/2);
            o[rt*2]+=o[rt];
            o[rt*2+1]+=o[rt];
            o[rt]=0;
        }
        if(L<=(l+r)/2)//二分思想,如果左边有点
        {
            find(ls,L,R);//那就找找左边
        }
        if(R>(l+r)/2)//如果右边有点
        {
            find(rs,L,R);//那就找找右边
        }
        su[rt]=su[2*rt]+su[2*rt+1];//还是那句老话,橘氏春秋有云:有下就有上
    }
    return;//看到return我就开心↖(^ω^)↗
}

哇吼,结束了才怪,接下来是总代码!

//线段树要写成lazy[i]+=lazy[祖先]的形式
//温馨提示,炒鸡重要,我这个蒟蒻就被坑了嘤嘤嘤
#include<iostream>
#include<cstdio>
#define ls 2*rt,l,(l+r)/2
#define rs 2*rt+1,(l+r)/2+1,r
#define ll long long
using namespace std;
int n,m,a,c;
ll su[400005],x,y,k,ans[100005],o[400005];//数组开4倍
void build(ll rt,ll l,ll r)
{
    if(r==l)
    {
        scanf("%lld",&su[rt]);
    }
    else
    {
        build(ls);
        build(rs);
        su[rt]=su[2*rt]+su[2*rt+1];
    }
    return;
}
void change(ll rt,ll l,ll r,ll L,ll R,ll add)
{
    if(l>=L&&r<=R)
    {
        su[rt]+=add*(r-l+1);
        o[rt]+=add;
        return;
    }
    if(o[rt]!=0)
    {
        su[rt*2]+=o[rt]*((r+l)/2-l+1);
        su[rt*2+1]+=o[rt]*(r-(r+l)/2);
        o[rt*2]+=o[rt];
        o[rt*2+1]+=o[rt];
        o[rt]=0;
    }
    if(L<=(l+r)/2)
    {
        change(ls,L,R,add);
    }
    if(R>(l+r)/2)
    {
        change(rs,L,R,add);
    }
    su[rt]=su[2*rt]+su[2*rt+1];
    return;
}
void find(ll rt,ll l,ll r,ll L,ll R)
{
    if(l>=L&&r<=R)
    {
        ans[c]+=su[rt];
    }
    else
    {
        if(o[rt]!=0)
        {
            su[rt*2]+=o[rt]*((r+l)/2-l+1);
            su[rt*2+1]+=o[rt]*(r-(r+l)/2);
            o[rt*2]+=o[rt];
            o[rt*2+1]+=o[rt];
            o[rt]=0;
        }
        if(L<=(l+r)/2)
        {
            find(ls,L,R);
        }
        if(R>(l+r)/2)
        {
            find(rs,L,R);
        }
        su[rt]=su[2*rt]+su[2*rt+1];
    }
    return;
}
int main()
{
    scanf("%d %d",&n,&m);//n个基本点,m次操作
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&a);
        if(a==1)//我们要进行区间加啦
        {
            scanf("%lld %lld %lld",&x,&y,&k);//在x到y上加k
            change(1,1,n,x,y,k);
//            for(int i=1;i<=2*n;i++)cout<<" "<<i<<"="<<su[i];
//            cout<<"\n";
//            写给需要调试的小可爱的
        }
        if(a==2)//查询
        {
            c++;//个人喜欢统一输出,c记录第几次询问
            scanf("%lld %lld",&x,&y);//查询x到y的和
            find(1,1,n,x,y);
        }
    }
    for(int i=1;i<=c;i++)
    {
        printf("%lld\n",ans[i]);//统一输出答案
    }
}

这样,一棵完完整整的基础简化版线段树就写完了

有问题的话可以问呦~虽然我也不一定会但是我会尽力解答的!

感谢阅读

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:抽象类和接口都不能被实例化

下一篇:Pots POJ - 3414 (搜索+记录路径)