线段树

Mr_HY43205 · 2021-08-16 22:33:02 · 个人记录

前言

线段树是算法竞赛中一种常用且高效的数据结构。然而，目前有关线段树的资料，内容大多只注重线段树实现上的一个部分。本文从原理出发，尽量包含了线段树有关的常见内容，提供了一些理解线段树的角度。

0 目录

1. 线段树的基本原理

2. 线段树的优化

3. 线段树的拓展

4. 线段树的应用

5. 总结

1 线段树的基本原理

本节主要从原理角度分析线段树的思想方法以及运作方式，较为详细地解释了线段树是如何解决一些特定问题的。

1.1 线段树解决什么问题？

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

线段树是一种数据结构，用来维护区间信息。一般来说，线段树支持区间修改和区间查询操作。

区间修改操作，包括：区间统一改成 d；区间加 d；区间乘 d；区间 \max/\min；区间按位与/或/异或等等。

区间查询操作，包括：区间和；区间积；区间最值；区间按位与/或/异或；区间 d 次方和；区间内连续段个数；区间 \gcd 等等。

使用线段树维护的信息，一般需要满足区间可加性，即通过区间 [a,b) 和区间 [b,c) 的信息可以求出区间 [a,c) 的信息。

一般来说，线段树可以分成两类：一类线段树维护序列上的区间信息，称为普通线段树；一类线段树维护可重集合上的区间信息，称为权值线段树。这两类线段树，维护的对象不同，其本质思想是一样的。

1.2 线段树的基本原理和思想

线段树是一棵二叉树，每一个节点记录一个区间内的信息。在对区间进行操作时，可以将一个大区间分解成 O(\log n) 级别个小区间进行操作。

对一个区间进行操作，若使用暴力操作，需要遍历区间中每一个元素，而线段树将大区间分解成几个小区间后，就可以只操作 O(\log n) 个小区间，从而提高了效率。

线段树的想法其实来源于分治思想，将一个序列进行分治从而将其分成形式相同，规模更小的子问题进行求解。将分治的过程形象化，把每一次递归得到的区间记录下来，则整个序列的递归树形成的就是一棵线段树。

1.3 时间/空间复杂度分析

1.3.1 时间复杂度分析

• 线段树的深度不超过 \log_2n-1 层。
• 对一次区间操作来说，这个区间在每一层内最多覆盖 2 个子区间，最多访问 4 个子区间的信息。
• 单次修改/查询的区间最多 4\log_2n-1 个，因此单次操作的时间复杂度为 O(\log n)。

线段树时间复杂度的极限情况：

1.3.2 空间复杂度分析

• 对于一棵 k 层的满二叉树来说，其总节点数为 2^0+2^1+2^2+\cdots+2^k=2^{k+1}-1。
• 对于一棵维护 [1,n] 区间的线段树来说，其最大规模为一棵 \log_2n 层的满二叉树，总节点数为 2^0+2^1+2^2+\cdots+2\log_2n=2n-1。
• 因此，线段树的空间复杂度为 O(n)。

1.3.3 问题：为什么不用 k 叉树实现线段树？

事实上在维护二维信息时，有时也会用到 4 叉的线段树，但在大部分维护线性信息时我们还是使用 2 叉树。

• 从时间复杂度上分析：
  • 深度不超过 \log_2k+1 层
  • 一次区间操作：每一层最多覆盖 2(k-1) 个区间，最多访问 2k 个子区间的信息。
  • 单次修改/查询时间最多为 2k\log_kn-k+1。
• 从空间复杂度上分析：
  • 最大规模，即满 k 叉树的总节点数为 k^0+k^1+k^2+\cdots + k^{\log_kn} = \left\lfloor\dfrac{n(1-n)}{1-k}\right\rfloor.
• 从代码实现上分析：
  • 如使用二叉树，可以通过位运算直接得到子区间的位置，而 k 叉树则需要进行多次除法运算，效率较低。

当 n=100000 时，程序运行时间随 k 增长的图像如下：

可以看到，从理论上来说，并不是 k 越小速度越快，但差别也不大，在 k=2 时位运算的效率提升和代码逻辑上的简洁完全可以弥补这一点点差距。

1.3.4 可以进行区间操作的一些数据结构比较

1.4 线段树的实现方法

这里主要指的是树结构的记录方法。（即建树方法）

每一个节点记录一个区间 [l, r]，维护这个区间所需要的信息。 一个节点的左子节点记录区间 [l, mid]，右子节点记录区间 [mid + 1, r]，其中 mid = l + \left\lfloor\dfrac{r-l}{2}\right\rfloor。

如何得到节点编号 i :

1. 根节点为 1，节点 i 的左儿子编号 2 × i，右儿子编号 2 × i + 1。（堆式建树）
2. 根节点为 1，对每个节点 i 分别记录其左儿子和右儿子编号 ls[i], rs[i]。（动态开点）
3. 对于区间 [l, r]，其节点编号 i 取决于其左端点 l 和右端点 r。

不同建树方法的空间比较：

1. 根节点为 1，节点 i 的左儿子编号 2 × i，右儿子编号 2 × i + 1。

   • 至多需要 2 × 2^{\left\lceil\log_2n\right\rceil} 空间，一般在使用时开 4n 大小的数组。

2. 根节点为 1，对每个节点 i 分别记录其左儿子和右儿子编号 ls[i], rs[i]。

   • 使用空间完全等于节点数（最多为 2n-1），直接开 2n 大小的数组就足够了。

3. 对于区间 [l, r]，其节点编号 i 通过左端点 l 和右端点 r 计算得到。

   • 取决于节点编号的计算方法，通常不会超过 2n 。

1.5 线段树复杂度保证：懒标记

之前提到，线段树将区间分段维护，在询问时通过合并区间来求出所需答案。懒标记在其中的作用就在于保证每次修改区间的完整性，使得复杂度不至于退化成 O(n)。

懒标记的维护方法一般有以下两种：

1. 当需要访问被 tag 覆盖区间的子区间时，将 tag 拆开，传递到子区间并更新子区间的信息。（标记下放）

   • 一般采用 push_down 函数进行

2. 在进行区间操作时不更新子区间信息，只在查询时统计区间内 tag 对答案的贡献。（标记永久化）

   • 当一个区间被完整地修改时更新 tag ，否则更新其维护信息。
   • 在查询时，如果有 tag 则计算 tag 对答案的贡献。

线段树操作的核心：

• 当且仅当区间整段被修改时更新懒标记。
  • 推论：只有单点修改时不需要懒标记。
• 修改时，在访问到一个区间以后，必须保证这个区间维护的信息是最新的。
• 需要计算懒标记的贡献（可以在更新标记时计算，也可以在查询时计算）。

2 线段树的优化

线段树在时间和空间方面的复杂度都非常优秀，但仍然有优化的空间，有时也可能会出现一些必须优化的情况。本节从时间和空间两个方面介绍线段树的一些优化方法。

2.1 运行时间优化（常数部分）

2.1.1 线段树运行时间的常数

描述线段树最坏情况下访问节点个数的函数是 f(n)=4\log_2n-1，自身常数为 4（实际上是 4\log_{2}10）。但这仅仅是不进行任何操作时的常数。如果在访问区间时考虑维护区间信息和懒标记的时间，线段树的常数远不止 4 倍。

按一个语句为一次操作来计算，粗略估计得出：普通维护区间和的线段树常数为 10。

2.1.2 线段树的自底向上版本

线段树的自底向上版本，也就是俗称的“zkw 线段树“。出自张昆韦的《统计的力量——线段树全接触》。

来源：张昆韦《统计的力量——线段树全接触》

其中给出了一种自底向上实现线段树的方法：首先将维护的值域 n 补成 2 的幂次，然后使用堆式建树。在这样的建树方式下，我们可以直接在线段树的最底层通过下标加 n 的方式找到原数组的对应位置。由此，我们可以直接找到所需维护区间 [l,r] 在线段树上对应的叶节点，从而进行自底向上的维护。

维护方法为：将原来所需维护的区间 [l,r] 转换为开区间 (l-1,r+1)，然后使用两个指针记录开区间的左端点和右端点，一直向上维护直到区间为空或到根。

由于需要将闭区间转成开区间，因此对于值域为 [1,n] 的区间，线段树的范围应该能记录 [0,n+1] 的信息。同时，由于这种线段树是自底向上维护的，所以需要记录懒标记就必须采用标记永久化的方法。

自底向上版本线段树具有常数小，代码短，便于调试等优点，但也有一定的限制，在此不做过多展开。

2.2 空间复杂度优化

对于一般的问题，线段树 O(n) 的空间复杂度已经足够优秀。但是，当维护的值域过大，如序列的长度为 10^9 或集合的值域为 [1, 10^9] 时，O(n) 的空间复杂度显然无法承受。因此，我们需要对其空间复杂度进行一些优化。

以下统一默认值域 n \leq 10^9，区间操作 q\leq 10^5。

一般来说，线段树的空间复杂度优化有两种：离散化和动态开点。

• 离散化：对于 q 次询问操作来说，其涉及到的区间端点最多 2q 个。因此，我们可以考虑将这些区间端点离散化，对离散化后的区间用线段树维护。

• 动态开点：可以发现，在操作次数远小于值域时，线段树中有相当一部分的节点不会被访问到。由此，我们可以只在访问到一个节点时才记录和更新其区间信息。想要实现这样的操作，我们需要使用之前提到的，对每个节点分别记录左右子节点编号的建树方法。

上表为线段树不同空间优化下的比较。

值得一提的是，动态开点虽然在时间和空间复杂度上都略差于离散化，但由于其可以支持在线的性质，相较于离散化有更广泛的应用场景。对于一些更高级的线段树操作，如线段树合并、可持久化线段树等，动态开点都是非常重要的实现方法。

3 线段树的拓展

线段树的结构使得我们可以利用线段树来完成一些高级操作，如线段树合并，可持久化，线段树分治等等。本节只简要介绍了一些线段树上的拓展操作，具体的实现细节需要参考更多资料。

3.1 线段树合并

有时，我们可能需要同时维护多棵线段树的信息。例如在一棵树上，对于树上的每一个节点维护一个集合，或者需要同时维护多个序列。这时候，一般的合并方法需要每次 O(n) 的时间进行维护。我们可以通过线段树合并的方法将其优化至均摊 O(\log n) 时间。

线段树合并，依赖于线段树形态的特殊性质：由于我们构造线段树时统一用的是以区间中点为分界的二叉树，因此对于值域相同的两棵线段树来说，其完整的形态应该完全相同。对于相同区间的操作，在两棵线段树上访问到的区间也应该完全相同。

来源：黄嘉泰《线段树的合并——不为人知的实用技巧》

将两棵线段树中对应节点合并的操作如下：（假设现在合并到的是 i_1 和 i_2 节点）

• 如果 i_1，i_2 中有一个节点为空，则返回另一个。
• 如果 i_1，i_2 都为叶节点，合并两个点的信息。
• 否则，分别递归合并两个节点的左右子节点，并更新本节点的信息。

可以得出，合并两棵线段树的时间复杂度与两棵树中重合的点数成正比。

想要进行线段树合并，我们需要在维护每个序列/集合时使用动态开点的线段树。假设有 q 次操作，值域为 n，需要维护的线段树数量也为 n。如果每次操作都是单点修改，那每次操作最多新增 \log_2n 个点；如果每次操作都是区间修改，那每次操作最多新增 4\log_2n 个点。因此，不管是单点修改还是区间修改，最终的总点数为 O(q\log n) 级别的。

此时将所有线段树全部合并，其时间复杂度也和所有树中重合的点数成正比，因此最坏时间复杂度为 O(q\log n)。

3.2 线段树分裂

线段树分裂是线段树合并的逆操作，将一棵线段树上的信息分成两棵来维护。

线段树分裂的操作一般来说不是很常见，而且也常和线段树合并的操作一起使用，可以将一棵线段树中记录 [l,r] 区间的所有节点移到新的线段树上。

将一棵线段树中某节点分裂出去的操作如下（假设现在要将 i_1 的信息转移到 i_2）：

• 如果 i_1 为空，直接返回。
• 如果 i_1 维护的区间被 [l,r] 包含，直接把 i_1 这个节点连向新的线段树，并把 i_1 和原来的线段树断开。
• 否则，分别递归分裂 i_1 的左右子节点，更新当前线段树和新线段树上对应节点的信息。

可见，线段树分裂的操作也依赖于同值域线段树形态相同的特殊性质，以及动态开点的实现方法。

单次线段树分裂的时间复杂度和线段树区间操作的时间复杂度相同，为 O(\log n)。对于 q 次查询来说，总时间复杂度还是 O(q\log n)。

3.3 线段树的可持久化

可持久化数据结构需要保存历史版本信息，并在某些情况下需要支持对历史版本的修改操作。所有历史版本都可查询和修改称为完全可持久化，而只有最新版本可以修改，历史版本只能查询称为部分可持久化。可持久化线段树支持的是完全可持久化。

对于线段树的可持久化，其思想是从暴力方法改进而来的。如果需要保存每一个历史版本的信息，朴素的想法是对每一个版本建立一棵线段树。在更新版本的时候复制一遍历史版本的信息。这样的做法时间和空间复杂度太高，难以接受。

从线段树性质的角度来看，每次通过修改获得一个新版本时，最多修改了 O(\log n) 个节点的信息。由此，我们可以将没有修改过的节点保留，只对修改过的节点开新空间。

来源：oi-wiki.org 数据结构 可持久化线段树

可持久化线段树，本质上是将两个版本中相同的节点合并，两个版本共用一些节点，从而达到节省空间和时间的效果。对于 q 次操作，值域为 n 的问题，可持久化线段树的总时间复杂度为 O(q\log n)。

事实上，由于重新连接线段树结构的原因，整张图严格来说并不能算是一棵“树”。同时，我们也可以发现，实现可持久化线段树需要动态开点的技术。

线段树的两种类型：普通线段树和权值线段树，可持久化的方法是相同的。有时，可持久化权值线段树也被称作“主席树”。

4 线段树的应用

线段树是一种十分灵活的数据结构。通过巧妙的设计，我们可以在其上记录各种各样的区间信息。本节列举李超线段树和吉如一线段树两个例子，以展示线段树的应用方式。这部分内容比较笼统，建议通过论文和其他资料了解更多细节。

4.1 李超线段树

李超线段树解决的问题是在平面直角坐标系中，插入一条线段（或直线），查询在某一位置上最高或最低的线段（或直线）。

不管是什么种类的线段树，维护的都是区间信息。在这个问题中需要维护的区间信息是对应区间中点上最优的线段。李超线段树的结构是将值域作为下标，区间中点二分。

当在一个区间中插入一根直线时，需要进行以下操作：

• 若该区间无最优直线，则该线段可以直接成为最优直线。
• 否则，设该区间的中点为 mid，我们拿新直线在中点处的值与原最优直线在中点处的值作比较。
  • 首先，如果新直线斜率大于原直线:
    • 如果新直线在 mid 处更优，则新直线在右半区间一定最优，旧直线在左半区间可能最优；
    • 反之，旧直线在左半区间一定最优，新直线在右半区间可能最优。
  • 如果新直线斜率小于原直线：
    • 如果新直线在 mid 处更优，则新直线在左半区间一定最优，旧直线在右半区间可能最优；
    • 反之，旧直线在右半区间一定最优，新直线在左半区间可能最优。

每次操作最多向下递归一层，因此插入一根直线所需总时间为 O(\log n)。

如果插入一根线段，根据线段树的性质，我们可以把线段覆盖的定义域在线段树上拆成至多 O(\log n) 个区间，然后分别在这些区间中插入直线即可。此时，总时间复杂度为 O(\log^2n)。

4.2 吉如一线段树

吉如一线段树解决的问题是对一个序列进行区间最值操作或记录历史最值。

对于个序列进行区间最值操作，我们需要额外统计如下几个量：该区间的最大值 ma、严格次大值 se、以及最大值的个数 t。

对于某一个区间取最值（假设将所有 a_i 变成 \min(a_i,x)），有以下操作：

• 如果 ma<x，显然这个 x 是没有意义的，直接返回；
• 如果 se<x<ma，这个 x 能更新当前区间中的最大值。于是我们让区间和加上 t\cdot(x-ma)，然后更新 ma 为 x，并打一个标记。
• 如果 x<se，那么这时你发现你不知道有多少个数涉及到更新的问题。此时，我们递归更新当前节点的左右儿子。

这个算法的时间复杂度为 O(m\log n)。

而对于历史最值问题，一般来说需要通过定义辅助数组 B 来将其转化为区间操作。

以上两种应用都属于对线段树的扩展。通过设计不同的维护信息和操作方式，线段树可以解决的问题范围十分广泛。只要深入了解了线段树的实现原理，就可以自行设计出不同的线段树操作。

5 总结

线段树在算法竞赛中应用较为广泛，且足够灵活。线段树的应用方式很多，但重点在于其分治式的结构以及维护标记等操作。限于篇幅，本文略过了线段树的具体实现操作以及代码部分，这些部分还需要结合其他论文等参考资料进行更深入的了解。

参考资料

1. 岳云涛《浅谈线段树在信息学竞赛中的应用》
2. 林涛《线段树的应用》
3. 张昆韦《统计的力量——线段树全接触》
4. 何琦《精细地实现程序——浅谈OI竞赛中的常数优化》
5. 徐寅展《线段树在一类分治问题上的应用》
6. 吉如一《区间最值操作与历史最值问题》
7. 黄嘉泰《线段树的合并》
8. 陈立杰《可持久化数据结构研究》
9. 托马斯·科尔曼、查尔斯·雷瑟尔森、罗纳德·李维斯特、克利福德·斯坦《算法导论》
10. 李煜东《算法竞赛进阶指南》
11. oi-wiki 数据结构部分