标签：浅谈 val int 线段 mid seg 节点

浅谈线段树Segment_Tree

By xiaruize

引言

OI中,有一种好玩的游戏,叫做码线段树,那么线段树是什么???

线段树的目的

线段树主要用于在区间上动态维护一些值(如最大值,最小值,和,积等)

线段树的实现

以区间最大值为例,给定一个长度为 $n$ 的数组,每次查询求 $[l,r]$ 之间的最大值,或将 $[l,r]$ 赋值为 $val$

显然,如果暴力去维护这个问题,需要 $O(NQ)$ 的时间复杂度, 并不能解决$1 \leq n,q \leq 10^5$级别的问题

此时,我们考虑将原问题分解为 ($[l,mid]$ 的 $max$ 与 $[mid+1,r]$ 的 $max$) 的 $max$

接着,我们可以以此类推,细分到只有一个节点

当 $n=6$ 时, 线段树如下图

{% asset_img seg1.png n=6时的线段树形态 %}

线段树的存储

一般线段树使用和二叉树类似的方式存储 注意4倍空间

这样存储的好处在于,对于点$p$, 它的左儿子是$ p<<1 $, 右儿子是 $p<<1|1$, 父节点是 $p>>1$

建议使用define定义ls,rs为左右儿子

上传pushup

该操作用于通过$p$节点的儿子更新$p$节点

以求最大值为例

void pushup(int p)
{
    seg[p].val=max(seg[ls].val,seg[rs].val);
}

建树 build

首先,肯定需要建树,递归即可

void build(int l,int r,int p)
{
    seg[p].l=l;
    seg[p].r=r; //可以放在函数的参数里
    if(l==r) //到叶子节点
    {
        seg[p].val=a[l]; //赋值
        return;
    }
    int mid=(l+r)>>1; //不打括号也可以,+的优先级比>>高
    build(l,mid,ls); //处理左儿子
    build(mid+1,r,rs); //处理右儿子
    pushup(p); //更新当前节点
}

也可以将当前的区间放在参数里,主要看个人习惯

修改update

单点修改

如果只需要修改一个点,那么可以通过 $l,r$ 的指引, $dfs$ 到这个点,修改它的值,返回时进行一遍 $pushup$

void update(int p,int d,int val)
{
    if(seg[p].l==seg[p].r) //到达需要修改的节点
    {
        seg[p].val=d;
        return;
    }
    int mid=seg[p].l+seg[p].r>>1;
    if(d<=mid)//在左侧
        update(ls,d,val);
    if(d>mid)//在右侧
        update(rs,d,val);
    pushup(p); //更新当前节点
}

区间修改(lazy tag)

我们在回头看一下题目,发现需要支持区间修改,如果做$n$次单点修改,会消耗大量的时间

此时,我们可以在一段在子节点都需要修改的节点上打一个懒标记(lazy tag),表示当前节点及下属的节点都需要修改

例如,修改区间[1,5]为2

这样,可以用更优的速度完成修改操作

void update(int u, int l, int r, int d)
{
    if (tr[p].l >= l && tr[p].r <= r)  //更新节点并打懒标记
    {
        tr[p].val=max(tr[u].val,d);
        tr[p].laz=max(tr[u].laz,d);
    }
    else
    {
        pushdown(p); //见下方
        int mid = tr[p].l + tr[p].r >> 1;
        if (l <= mid) update(ls, l, r, d); //左侧存在需要修改的节点
        if (r > mid) update(rs, l, r, d); //右侧存在需要修改的节点
        pushup(p); //更新当前节点
    }
}

下传懒标记pushdown

如果你认真阅读了上面的代码,会发现pushdown函数并没有讲过

那么pushdown的作用其实是下传懒标记

及将父亲节点记录的修改(laz)传给儿子

void pushdown(int p)
{
    seg[ls].laz=seg[p].laz;
    seg[ls].val=seg[p].laz;
    seg[rs].laz=seg[p].laz;
    seg[rs].val=seg[p].laz;
    seg[p].laz=0;
}

查询 query

那么,已经有了一棵线段树,要如何查询区间最值呢?

可以去模仿update操作,每次询问左区间和右区间,在合并答案

int query(int l,int r,int ll,int rr,int p) //把当前区间放在了参数里的写法
{
    if(l>=ll&&r<=rr)
    {
        return seg[p].val; //到达节点,返回答案
    }
    int mid=(l+r)>>1;
    int res=0;
    pushdown(p);//下传懒标记
    if(mid<rr)
        res=max(res,query(mid+1,r,ll,rr,rs)); //通过左区间更新
    if(mid>=ll)
        res=max(res,query(l,mid,ll,rr,ls)); //通过右区间更新
    return res;
}

读到这里,你应该已经可以基本掌握如何码线段树. 但是,要在码线段树的游戏中超过你的同伴,你需要多加练习

标签：浅谈,val,int,线段,mid,seg,节点
From： https://www.cnblogs.com/xiaruize/p/16804503.html

浅谈线段树