【算法笔记】线段树

前言：

以前有一段时间喜欢疯狂往后学东西。

但是学了只会贺一贺模板的题解代码。

变个花样就不会做了。

现在有时间，那么就下点功夫搞懂这些东西吧youl。

线段树 Segment Tree

这是个很厉害的数据结构。

把它叫做 \(\texttt{DataStructure}\) 完全制霸的第一步完全不为过。

你会发现，它广泛的出现在各种维护区间信息的题目当中。

用法特别多（树剖+线段树，线段树套平衡树，权值线段树……）yun

但实际上它真的很简单 qq。

基本结构

它是一种基于分治思想的结构。

简单来说，它将一个序列从中间切开。

然后再把切开之后的一半的序列再折半。

这么递归下去一直到每个切出来的小块都是一个元素。

也就是一个 \(l=r\) 的区间。（叶子节点）

每一个节点会维护一个区间的 信息。

这个信息可以是区间和，区间 \(\min\) 值，区间 \(\sin\) 和等等。

那么你在维护不同的信息的时候直接改一改维护的方式就好（运算符/计算方法）

我们从区间的角度来看，它是这样子的。

cSn8qf.png

然后从二叉树的角度看就是这样的

cSnJZ8.png

这里 \(\text{dat}\) 表示的是它维护的是哪个区间的信息，我省略了一部分。

写法就是 \([l,mid],[mid+1,r]\)

（就直接写 mid=(l+r)>>1 即可，\(\texttt{C++}\)会自动取整）

很明显，如果说序列并不是长度为 \(2^n\) 的序列的话，

那么它的最后一层节点就会出现空余。

假设我们这样子按顺序给它的节点标个号，

cSntIg.png

你会发现对于任意一个非叶子节点，都有这样子的结构：

cSnYdS.png

（当然也可以用位运算写成：x<<1 和 x<<1|1）

也就是说，只要知道父亲节点的编号，那么左右儿子的编号就能用这种“二倍标记法”求出来。

那我们可以直接用一个结构体来储存线段树。

上面保存了它的 \(\text{l,r,dat,value,pos}……\)

对于 \(\text{pos}\) ，我们可以直接用上图的 “公式” 计算。

（有的写法是把 \(\text{pos,l,r}\) 直接作为函数的参数传递，就不用在结构体里面写）

要注意的一个点是，我们至少需要四倍空间才不会炸掉。

证明如下：

因为线段树是一颗二叉树，且底层共 \(n\) 个节点

所以线段树的高度是 \(\left\lceil \log_2n \right\rceil\)

层数是 \(\left\lceil \log_2n \right\rceil +1\)

你会发现线段树最左边的几个节点编号组成了一个等比数列 \(1,2,4,8......\)

而且每个节点的编号就直接表示了它所在的层的节点个数（前提是这一层节点都没有空余）

那么，根据等比数列求和公式 \(\dfrac{a_1\times(1-q^x)}{1-q}\) 以及线段树的左右儿子标记方式：

则有：\(\dfrac{1 \times(1-2^{\left\lceil \log_2n \right\rceil +1})}{1-2}\)

\(=2^{\log_{2}n+2}-1 \approx 4\times n\)

看不懂？

没关系。

还记得刚才我说的：

如果说序列并不是长度为 \(2^n\) 的序列的话，

那么它的最后一层节点就会出现空余。

吗？

当 \(n=10\) 的时候（这里的标记写法和我不太一样，不过无伤大雅）（其实我感觉这里是写错了，感性理解就行）：

WyI5q0.png

(图源自某著名github讨论（已删帖）)

你看最后一层是不是有空缺？

按照编号法则，底层最右边那个节点竟然是 \(31\) !!11

再扩展到更大的情况，就有可能出现接近 \(4\times n\) 的数据，所以四倍空间还是有必要的。

然后定义的话就这么写（define是为了调试方便）：

#define l(o) t[o].l
#define r(o) t[o].r
#define sum(o) t[o].value
#define tag(o) t[o].lazy
#define lson(o) o<<1
#define rson(o) o<<1|1
struct segment_tree{
    int l,r;//dat interval
    int value,lazy;
}t[si*4];

操作

建树

我们清楚，一个非 \(l=r\) 节点（非叶子）的信息是要由它的左儿子和右儿子合并而成的。

（这个比较显然，从前面就可以看出来）

那我们递归下去。

也就是说只需要让这个区间的信息等于它左右儿子合并之后的信息。

那么上传信息 (Pushup) 的时候，

维护区间 \(\min\) 就是这样的：minv(fa)=min(minv(ls),minv(rs));

区间和就是 sum(fa)=sum(ls)+sum(rs);

WgQ8i9.png

当然为了更新我们要层层递归（

递归边界就是 \(l=r\) 的叶子节点。

单点修改

从上面的内容可以知道一个叶子节点的信息是会被它上层的 \(\log(n)-1\)个 节点包含的。

也就是说叶子节点信息的改变会导致覆盖它的所有区间的信息也改变（有可能不变，但是你还不是要向上更新）。

所以在修改的时候要一起修改它的上层节点信息（Pushup）。

找叶子结点的时候判一下 \(\text{pos}\) 在左子树还是右子树，然后递归。

WgllOf.png

不过在维护一些特殊信息是需要保留序列的原值来修改的。

这时候多加一个维护信息和原信息即可。

区间查询

一个区间被查询的时候，在线段树里有这么几种情况。

  1. 当前递归到的节点所维护的区间 \([l,r]\) 直接被查询的区间覆盖（包含）完了。

    因为这个区间的信息是完整的被需要的。

    我们直接把它的信息返回即可。

  2. 它并没有被一个节点直接完整包含：

    那么我们就需要分割了。

    用化整为零的思想，把这一个大区间拆成几个完整的小区间

    （也就是拆成树上的若干个节点）

    然后把这几个区间的信息合并成大区间的信息返回。

    如下图。

    Wg1jPJ.png

你会发现在每一个完整的节点处我都停止了。

其实就是满足了第一种情况\qq

而且到最后是一定满足第一种情况的，可以想想为啥（

所以我们直接判一下第一种条件（作为递归边界）

看一下这个区间要不要分割。

如果要分割的话我们就左右子树分别写递归查询。

注意这里左右子树的查询是相互独立的（上图区间第三行的递归），所以千万不要写 else。shqcy

单点查询可以写 else 是因为只有一个确定的点，不会同时递归到两个子树去。

还有，如果你这是在维护 \(\min\) 一类的东西。

你需要把它变成“候选”的，因为递归之后的其它区间可能有最值。(递归的时候取个 \(\min\) )

如果是维护“和差”一类的信息就不用了，直接加和即可\youl。

区间加（修改） & lazytag

重头戏来了。

我们知道如果你用暴力修改的话……

那么多子树（其实也不多，就是 一个稍微有点大的数\shq刀），早就爆掉了!

所以我在之前没提到但是写了的 lazytag 就要派上用场了 \cy。

我们设想，假设我们修改了节点 \(p\) 完全覆盖的一个区间 \([l,r]\)，
而且还递归搞了下子树。

但是我们之后没有用到这个区间的信息，那NMD不是浪费空间和时间么？？？

那么“延迟标记”就该出现啦！！！！！

我们设 \(\text{tag}[p]\) 表示 \(p\) 欠它的左右儿子一个更新。

比如维护区间和的时候，\(\text{tag}[p]=114514\) 就表示\(p\)这个节点的左右儿子都少了一个 \(\text{value}=114514\) 的值。

那么之后我们查询的时候如果发现它用到了。

下传标记，然后把自己的标记清除（烧债券gx），然后把标记传递给左右儿子。

当然标记下传之后我们也要把左右儿子维护的信息更新。

举个例子。

Wg3Xef.png

update value 那里用 \(v\times\) 区间长度，

是因为整个区间都被加了 \(v\) 。

所以 \(\text{sum}\) 要加 \(v\times\) 区间长度（元素个数）（废话）。

这个地方 update 的做法要看题目情况而定。

因为出现了延迟标记这个玩意儿，

所以在之前的一些操作（查询，修改）里面就要加上打标记和下传标记。

现在区间加就很简单啦，如果完全覆盖，那么返回，反之打 \(\text{tag}\) 并递归（也就是和区间查一个道理）。

递归完之后再 Pushup 一下即可。

Code （维护区间和）


#include
using namespace std;

#define int long long // Remember to use %lld!
#define l(o) t[o].l
#define r(o) t[o].r
#define sum(o) t[o].value
#define tag(o) t[o].lazy
#define lson(o) o<<1
#define rson(o) o<<1|1

const int si=4e5+10;
int n,m,a[si];
struct segment_tree{
    int l,r; // Data interval
    int value,lazy; // Information & Lazytag
}t[si*4]; // One fourth larger space 

inline void pushdown(int p){
    if(tag(p)){
        sum(lson(p))+=tag(p)*(r(lson(p))-l(lson(p))+1);
        sum(rson(p))+=tag(p)*(r(rson(p))-l(rson(p))+1); // Update information
        tag(lson(p))+=tag(p),tag(rson(p))+=tag(p); // Spread tag 
        tag(p)=0; // Delete
    }return;
}
inline void build(int p,int l,int r){
    l(p)=l,r(p)=r,tag(p)=0;
    if(l==r){
        sum(p)=a[l];return;
    } // Or a[r](value of leaf)
    int mid=(l+r)>>1;
    build(lson(p),l,mid);
    build(rson(p),mid+1,r);
    sum(p)=sum(lson(p))+sum(rson(p)); // Pushup(or minv,maxv,sin,cos...)
}
inline void modify(int p,int x,int val){
    int l=l(p),r=r(p);
    if(l==r){ //Find leaf
        sum(p)=val;return; //Here is CHANGE x to val
    }
    int mid=(l+r)>>1;
    if(x<=mid) modify(lson(p),x,val); // In leftson
    else modify(rson(p),x,val); // In rightson
    sum(p)=sum(lson(p))+sum(rson(p)); // Pushup
}// It isn't need Pushdown because we will only change leaf node
inline int query(int p,int l,int r){
	int res=0,nl=l(p),nr=r(p); 
    if(l<=nl && nr<=r) return sum(p);
    pushdown(p);
    int mid=(nl+nr)>>1;
    if(l<=mid) res+=query(lson(p),l,r);
    if(r>mid) res+=query(rson(p),l,r);
    return res;
}
inline void update(int p,int l,int r,int v){
    int nl=l(p),nr=r(p);
    if(l<=nl && nr<=r){
        sum(p)+=v*(nr-nl+1);tag(p)+=v;
        return;
    }// Here is to ADD v for all elements in Interval[l,r]
    pushdown(p); 
    int mid=(nl+nr)>>1;
    if(l<=mid) update(lson(p),l,r,v);
    if(r>mid) update(rson(p),l,r,v);
    sum(p)=sum(lson(p))+sum(rson(p));
}

signed main(){
    scanf("%lld%lld",&n,&m);
    for(register int i=1;i<=n;++i){
       scanf("%lld",&a[i]);
    }
    build(1,1,n);
    while(m--){
        int op,l,r,k;
        scanf("%lld%lld%lld",&op,&l,&r);
        if(op==1){
            scanf("%lld",&k);
            update(1,l,r,k);
        }
        else printf("%lld\n",query(1,l,r));
    }
    return 0;
}

Tips

关于复杂度

所有的查询和修改操作正常来说都是

\(\text{O} (\log \text{n})\) 的 tyt，因为线段树的深度就是 \(\log (\text{n})\)。

而且递归到叶子节点就会回溯更新答案（废话）

注意事项

线段树其实就是一个维护区间信息（当然最好是满足“区间可加性”的条件）的工具。

可能是 \(\gcd,\min,\max,\sin,\cos,\operatorname{sum},\operatorname{powsum}\) 等等。

根据情况修改代码就可以实现。qiang

当然如果你遇到只有查询操作的时候而且信息也满足区间可加性，建议直接使用 ST 表。

  • 建树就是直接赋值（因为是单点）（后面那里和上传一个道理）。

  • Pushdown 就是给原信息加上 \(\text{tag}\) 里的信息或者更新最值,然后再把 \(\text{tag}(p)\) 下放并清空。

  • 上传合并(Pushup)就是把 \(p\) 这个元素用它的左右子树信息更新（取最值 or 加上去 or 其他）

  • 查询直接递归查一下然后 return res 就可以 ( \(res\) 可能在分开递归的时候求和或者最值之类的)。

  • 区间修如果是要更新（完全覆盖了），那么把原来的值加上新加的值（更新）（或者取最值），再把 \(\text{tag}(p)\) 变成 \(v\)。

这里的区间修指区间加，即是 \(\text{tag}(p)\) 是“要加上多少”，所以子树的 \(\text{tag}\) 是 +=（因为子树自己原来也可能有标记）。

如果是把整个区间全部变成一个数那么 \(\text{tag}(p)\) 就是改为多少。

那么你的区间修就直接赋值了（和建树一个道理）（直接覆盖，子树的 \(\text{tag}\) 就没用了）。

然后发现网上维护最值的代码没有在 pushdown 里面给 \(\max, \min\) 取最值，而是直接加上 \(\text{tag}(p)\)。

原因很简单，这里区间加了之后平均数增加方差不变（内卷），所以最小值最大值都是原来的基础上加了 \(\text{tag}(p)\)。

我们就没有必要再取一遍最值了 \heart。

也就是这样的:

void pushdown(int p){
	if(tag(p)){
		minv(lson(p))+=tag(p),minv(rson(p))+=tag(p);
		tag(lson(p))=tag(rson(p))=tag(p);
		tap(p)=0;
	}
}

然后修改里面：

	if(l<=nl&&nr<=r){
		minv(p)+=v,tag(p)=v;
		return;
	}
	//......
	minv(p)=min(minv(lson(p)),minv(rson(p)));

查询什么的就是：

inline int query_max(int p,int l,int r){
	int res=-0x7f7f7f7f,nl=l(p),nr=r(p); 
	if(l<=nl&&nr<=r) return maxv(p);
	int mid=(nl+nr)>>1;
	if(l<=mid) res=max(res,query_max(lson(p),l,r));
	if(r>mid) res=max(res,query_max(rson(p),l,r));
	return res;
}

inline int query_min(int p,int l,int r){
	int res=0x7f7f7f7f,nl=l(p),nr=r(p); 
	if(l<=nl&&nr<=r) return minv(p);
	int mid=(nl+nr)>>1;
	if(l<=mid) res=min(res,query_min(lson(p),l,r));
	if(r>mid) res=min(res,query_min(rson(p),l,r));
	return res;
}

有的题有区间乘（P3373），多加一个 \(\text{tagmul}\) 然后注意更新方式（先乘后加）即可。

还有，比如维护 sin 的时候，（有两个要相互更新的 \(\text{tag},\text{val}\)）

一定要先保存没被更新过的状态再更新另一个 \(\text{tag},\text{val}\) ！！！1111

我之后会找时间写上。(可能咕咕咕了)lh

扫描线

太菜了没写 \kk

一些犯过的错：

Yoomu

  1. build() 里面不给 l(p),r(p) 赋值。
  1. lson(p)写成 p>>1 （方向反了）
  1. 维护信息的时候如果是单点修改，完全可以不用lazytag，而且也不用维护一个原序列的值（因为当 p 是叶子节点的时候maxv(p)就是a[p]）
  1. 搞不清楚是区间加还是区间修。
  1. 该写 pushdown 不写，不用写 pushdown 非要写。
  1. 忘记 pushup。

例题：

  • P3372 【模板】线段树 1

  • P3373 【模板】线段树 2

  • P6327 区间加区间sin和

  • P1471 方差

  • P1531 I Hate It

  • P1883 函数

  • P1972 [SDOI2009]HH的项链

  • P2023 [AHOI2009] 维护序列

  • P1886 滑动窗口 /【模板】单调队列

（2021/2/15初稿，2021/7/24进行了一番大改）

Algor-线段树Cate-数据结构Type-算法笔记

相关

标签