线段树 | Serendipity

type

status

date

slug

summary

简介

线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。

线段树可以在的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。

线段树将每个长度不为1的区间划分成左右两个区间递归求解，把整个线段划分为一个树形结构，通过合并左右两区间信息来求得该区间的信息。这种数据结构可以方便的进行大部分的区间操作。

过程

有个大小为的数组，要将其转化为线段树，有以下做法：设线段树的根节点编号为，用数组来保存我们的线段树，用来保存线段树上编号为的节点的值，这里每个节点所维护的值就是这个节点所表示的区间总和。如图所示:

实现代码：

关于线段树的空间:如果采用堆式存储（是的左儿子，是的右儿子），若有几个叶子结点，则数组的范围最大为。

分析：容易知道线段树的深度是的，则在堆式储存情况下叶子节点（包括无用的叶子节点）数量为个，又由于其为一棵完全二叉树，则其总节点个数。当然如果你懒得计算的话可以直接把数组长度设为，因为的最大值在时取到，此时节点数为。

而堆式存储存在无用的叶子节点，可以考虑使用内存池管理线段树节点，每当需要新建节点时从池中获取。自底向上考虑，必有每两个底层节点合并为一个上层节点，因此可以类似哈夫曼树地证明，如果有个叶子节点，这样的线段树总共有个节点。其空间效率优于堆式存储，并且是可能的最优情况。

区间修改懒惰标记

如果要求修改区间，把所有包含在区间中的节点都遍历一次、修改一次，时间复杂度无法承受。我们这里要引入一个叫做懒惰标记的东西。

懒惰标记，简单来说，就是通过延迟对节点信息的更改，从而减少可能不必要的操作次数。每次执行修改时，我们通过打标记的方法表明该节点对应的区间在某一次操作中被更改，但不更新该节点的子节点的信息。实质性的修改则在下一次访问带有标记的节点时才进行。仍然以最开始的图为例，我们将执行若干次给区间内的数加上一个值的操作。我们现在给每个节点增加一个t，表示该节点带的标记值。最开始时的情况是这样的：

现在我们准备给[3,5]上的每个数都加上 5。根据前面区间查询的经验，我们很快找到了两个极大区间和。我们直接在这两个节点上进行修改，并给它们打上标记。

我们发现，3号节点的信息虽然被修改了（因为该区间管辖两个数，所以加上的数是），但它的两个子节点却还没更新，仍然保留着修改之前的信息。虽然修改目前还没进行，但当我们要查询这两个子节点的信息时，我们会利用标记修改这两个子节点的信息，使查询的结果依旧准确。

接下来我们查询一下区间上各数字的和。

我们通过递归找到区间，发现该区间并非我们的目标区间，且该区间上还存在标记。这时候就到标记下放的时间了。我们将该区间的两个子区间的信息更新，并清除该区间上的标记。

现在 6、7两个节点的值变成了最新的值，查询的结果也是准确的。

代码实现：

区间查询

一般地，如果要查询的区间是，则可以将其拆成最多为个极大的区间，合并这些区间即可求出的答案。

实现代码：

动态开点线段树

前面讲到堆式储存的情况下，需要给线段树开大小的数组。为了节省空间，我们可以不一次性建好树，而是在最初只建立一个根结点代表整个区间。当我们需要访问某个子区间时，才建立代表这个区间的子结点。这样我们不再使用和代表结点的儿子，而是用和记录儿子的编号。总之，动态开点线段树的核心思想就是：结点只有在有需要的时候才被创建。

单次操作的时间复杂度是不变的，为。由于每次操作都有可能创建并访问全新的一系列结点，因此 m 次单点操作后结点的数量规模是。最多也只需要个结点，没有浪费。

单点修改

区间查询

区间修改也是一样的，不过下放标记时要注意如果缺少孩子，就直接创建一个新的孩子。或者使用标记永久化技巧。

一些优化

这里总结几个线段树的优化：

在叶子节点处无需下放懒惰标记，所以懒惰标记可以不下传到叶子节点。

下放懒惰标记可以写一个专门的函数 pushdown，从儿子节点更新当前节点也可以写一个专门的函数 maintain（或者对称地用 pushup），降低代码编写难度。

标记永久化：如果确定懒惰标记不会在中途被加到溢出（即超过了该类型数据所能表示的最大范围），那么就可以将标记永久化。标记永久化可以避免下传懒惰标记，只需在进行询问时把标记的影响加到答案当中，从而降低程序常数。具体如何处理与题目特性相关，需结合题目来写。这也是树套树和可持久化数据结构中会用到的一种技巧。

模板例题

【模板】线段树 1 - 洛谷

https://www.luogu.com.cn/problem/P3372

【模板】线段树 2 - 洛谷

https://www.luogu.com.cn/problem/P3373