ConanKIDの小窝

ConanKIDの小窝

线段树 学习笔记

posted on 2020-09-14 13:44:42 | under 学习笔记 |

0. 闲话

哎呀,这篇博客之前由于种种原因咕了很久,现在必须要写了,教练交代的任务呀$QwQ$

1. 引入

教练:现在有一个序列,需要多次给这个序列的一段区间内的数都加上一个值。

我:这不是差分嘛!

教练:那如果我要多次输出序列呢?差分的效率不高呀?

我:……

教练:可以使用线段树。

2. 介绍

线段树其实就是一棵用来维护原数组区间修改和询问的二叉树,基于分治的思想。树上的每一个节点都管辖了原数组的某个区域。根节点的管辖区域是$[1,n]$($n$为原数组的元素个数)。

对于每个非叶子的节点的管辖区域$[l,r]$,他左孩子管辖的区域是$[l,mid]$,右孩子管辖的区域是$[mid+1,r]$(其中$mid=[\dfrac{l+r}{2}]$)。下图是当$n=6$时的树。 可以看出,除最后一层外,整棵树一定是完美二叉树。因此,可以将根节点编号为$1$,对于每个节点$k$,将左孩子编号为$2k$,右孩子编号为$2k+1$。

线段树有很多应用,下面统一以求区间和的问题作为例子讲述。

3. 建树

建树要干嘛?

定义一个$tree$数组,$tree_k$表示线段树上$k$号节点管辖的区间和。建树实际上就是要我们把所有$tree$给更新掉嘛。

首先,树上的叶子结点$k[x,x]$,$tree_k$就等于$a_x$。这是显然的。

对于非叶子结点$k[l,r]$,$tree_k=tree_{2k}+tree_{2k+1}$。根据定义,结论显然。

那么我们可以从根节点开始,递归每个节点的左孩子和右孩子,并在回溯时更新当前节点的$tree$值。当碰到叶子节点时,停止递归。

代码奉上。

(这里定义了一个$pushup$函数,其实就是将$tree_k$更新。)

void build(int k,int l,int r){//k节点管辖[l,r]区间
    if(l==r){//当前节点管辖的区域只有一个元素
        tree[k]=a[l];
        return;//更新之后return
    }
    int mid=(l+r)>>1;
    build(2*k,l,mid);
    build(2*k+1,mid+1,r);//递归左右孩子继续建树
    pushup(k);//回溯时将tree更新
} 

4. 区间询问

区间询问是一条形如qx qy的指令,表示询问区间$[qx,qy]$的元素之和,即$\sum_{i=qx}^{qy} a_i$。

定义函数$query(k,l,r,qx,qy)$表示节点$k$管辖的区域$[l,r]$与要询问的区间$qx,qy$交叉的部分的区间和。最后的答案显然是$query(1,1,n,qx,qy)$。

接下来分三种情况讨论。

  1. 两个区间完全没关系,即$qx>r$或$qy<l$,则return 0

  2. $[qx,qy]$包含$[l,r]$,即$qx \le l ,r\le qy$,则return tree[k]

  3. 两个区间有交叉,则递归查询$k$的左右孩子与$[qx,qy]$交叉部分的区间和,再相加,就是答案。如果一直递归下去,总有回到上述两种情况的那一天。

一直递归就好了。

注意,下面的代码中有一个地方空缺,是什么呢?那是本人埋下的伏笔。

int query(int k,int l,int r,int qx,int qy){
    if(qx>r||qy<l)return 0;
    if(qx<=l&&qy>=r)return tree[k];
    //???
    int mid=(l+r)>>1;
    return query(2*k,l,mid,qx,qy)+query(2*k+1,mid+1,r,qx,qy);
}

5. 懒标记&区间修改

区间修改,就是对原数组的一段区间内的数都加上$x$。

懒标记是对区间修改的一个优化。试想一下,原数组中,如果我对同一个区间内的数修改$s$次,每次都加上$1$,那样的时间复杂度太高了。实际上我们只要修改一次,给这段区间内的数加上$s$就行了。

如何实现呢?定义一个$tag$数组,$tag_k$表示线段树上$k$号节点管辖的区域要加上的数的和。每次给$tag_k$加上$v$时,$tree_k$也要加上$(r-l+1)\times v$($l,r$为$k$节点管辖区域的左右端点),因为原数组内$[l,r]$中的每一个数都加上了$v$。我们把这两行打包成一个$addtag$函数,便于操作。

void addtag(int k,int l,int r,int val){
    tag[k]+=val;
    tree[k]+=(r-l+1)*val;
}

当然,$k$节点还要把自己的$tag$下传。如果$k$有一个消息,他总要告诉自己的下级啊。

定义一个$pushdown$函数,表示把$k$节点的标记下传。只要把$k$的左右孩子$addtag$,就实现了这个操作。

void pushdown(int k,int l,int r){
    if(tag[k]==0)return;//如果tag[k]为0,就不需要下传懒标记
    int mid=(l+r)>>1;
    addtag(2*k,l,mid,tag[k]);
    addtag(2*k+1,mid+1,r,tag[k]);//给左右孩子分别addtag
    tag[k]=0;//注意,由于tag[k]已经下传过了,所以一定要清零
}

好了,我们终于可以讨论区间修改了码字真累

区间修改跟询问一样,分同样的三种情况。定义$update$函数,$update(k,l,r,qx,qy,val)$意义同$query$,只增加了一个$val$表示要给$[qx,qy]$内的数加上$val$。

  1. 两个区间完全没关系,即$qx>r$或$qy<l$,则直接return

  2. $[qx,qy]$包含$[l,r]$,即$qx \le l ,r\le qy$,本来是要继续递归的,但是我们有了懒标记,可以直接将$k$节点$addtag$。

  3. 两个区间有交叉,则递归$k$的左右孩子进行修改。一直递归下去,总有回到前两种情况的那一天。

注意下面的代码中有一个空白$QwQ$

void update(int k,int l,int r,int qx,int qy,int val){
    if(qx>r||qy<l)return;//1号情况
    if(qx<=l&&qy>=r){//2号情况
        addtag(k,l,r,val);
        return;
    }
    //???
    int mid=(l+r)>>1;
    update(2*k,l,mid,qx,qy,val);
    update(2*k+1,mid+1,r,qx,qy,val);//递归左右孩子
    pushup(k);//注意这一行很重要,如果不写这一行,线段树上的节点值就永远不会更新,修改就没用了
}

6. 收尾

现在我们只剩下一个问题了。

Q:$query$和$update$中留下的那个空白,是用来干嘛的?

A:$pushdown$。

如果我们不$pushdown$,那么$tag_k$就永远无法成为实质性的东西而是一直停留在$k$号节点,正确性就会出现问题,懒标记就失去了意义。而且,我反正是要继续往左右孩子递归下去的,那么不如在这个过程中,顺便把$tag$给下传一下,这样也会比在别的地方$pushdown$快一点。所以在两个函数里面$pushdown$,既保证了算法的正确性,又让时间得以优化。一石二鸟。

还有一个很重要的细节就是$tree$和$tag$数组要开$4n$的大小。

至此,线段树就被我们搞定啦。

完结撒花