C＋树进阶系列之深入线段树和它的延迟更新

1. 前言

和有相似之处，可以用于解决的问题。

但两者又各个千秋，树状数组本质是数组，有着树的形，可以借用树的一些概念。线段树是典型的二叉树结构，无论神和形都是树，可以应用树的所有理论。

本文将详细聊聊线段树。

2. 问题驱动

与树状数组一样，线段树可以缓存区间内具有特殊性质的数据（如：区间和，区间最值、…），以提高操作性能。

现通过一个案例理解的初衷。

如有如下数组，现有求任意区间内最大值的需求。最简单的解决方案是使用求最值，时间复杂度。

如果求某个区间中的最值是一个高频率操作，每次都使用穷举法计算，累积的时间代价是非常大的。

在代码中，当需要对相同的计算频繁调用时，首当其冲的想法必然是缓存机制。针对本题可以使用简单动态规划思想，缓存原数组中每一个位置的最大值。

输出结果：

缓存时间复杂度是，求最值时间复杂度为，如果原数组中的数据是稳定的，不失为一种良好的方案。

但是，如果原数组中的数据有频繁更新需求时，则需要随时联动更新整个缓存数组，时间性能会变得较大。

线段树的基本思路和树状数组一样，仅对区间信息缓存，更新也仅针对区间进行，线段树的时间复杂度为。

3. 线段树的构建流程

在探讨线段树的构建之前，先看一下最终线段树的形状。

分析结果图可知：

原数组中的每一个数据都是线段树的叶结点。

非叶结点的值是在其左、右子结点的值中选择了较大哪个。

结点至少包含 个信息。且叶结点的区间特征是左、右边界值相同。

整个数组就是一个大区间，区间边界从到，可统一描述格式为。

根据分析，构建的基本思路：

父结点向左、右子结点发送请求，获取左、右子结点上的值。

如果左、右子结点不是叶结点，则继续向自己的左、右子结点发送值的请求。

如果左、右子结点是叶结点，则把值回送给父结点。

父结点获取到左、右子结点值后，求两者中的最大值作为自己的值。

上面的过程显然符合递归的向后请求、向上回溯的执行模式。下面根据原数组提供的信息，使用递归思想构建出完整的线段树。

构建根结点，区间信息为 ，值未知。

构建根结点的左、右子结点。对根结点的区间使用二分思想，划分成左、右 个子区间，左区间范围，右区间范围，此时，左、右子结点点值任然未知。

以此类推，继续对非叶结点的区间信息采用二分思想，以子区间信息构建子结点。

直到区间不能再分（左、右边界相同），此时构建出来的结点是叶结点。以叶结点的区间值为索引号，从原数组中获取值。

然后把值向父结点提供，父结点会选择较大的值作为自己的值。

一路向上，直到根结点的值被填充。

最终可以看到构建出了一个满二叉树。

是不是对于任意一个数列中的数据都能构建出满二叉树？

不一定，只能说是一棵近似的完全二叉树。

因本例中数组恰好有 个数据。

根据二叉树的原理。树的深度为，时，深度。

而又知，二叉树的最后一层的结点数最多为 2h-1，把代入后可知值为。当最后一层达到最大数量时，此二叉树方为满二叉树。如果原数组中的数据只有 或其它个数，最后一层是不可能达到满二叉树所要的数量。

4. 线段树的 API

原数组中的数据个数不同，所构建出来的线段树不一定是满二叉树，或者说一定是完全二叉树，但也是一棵近似完全二叉树。因为完全二叉树中父结点和子结点的存在如下的位置关系。

如果父结点的位置为 。

如果存在左、右子结点，则左子结点的位置为 、右子结点的位置为 。

如果已知子结点的位置，则父结点的位置是 。根结点的父结点位置为 。

有了这个良好的数学关系，线段树常使用数组方式进行存储。

线段树的抽象。

4.1 结点类

结点类中有一个属性，称为延迟更新值，延迟更新是线段树的一个显著的特点。暂且不表，在线段树的区间更新时再深聊。

4.2 线段树类

4.2.1 初始化函数

使用递归初始化整个线段树。

测试构建线段树：

4.2.2 区间查询

查询指定区间中的最大值，需分几种情况讨论。

无效区间。如下图所示，中的或时。返回无解。

完整包含。当中的时。返回区间的最大值。

匹配左或右子区间。查找左、或右子空间中的最大值。

与左、右子空间相集。为左、右子空间中较大的值，即为区间最大值。

测试区间查找：

输出结果：

4.2.3 单点更新

单点更新某一个叶结点上的值。使用递归方案一路向下查询到叶结点，再在回溯过程中更新非叶结点。和初始线段树的逻辑相似。

测试单点更新：

输出结果：

当同时需要更新的叶结点较多时，因为单点更新的时间复杂度为，如果逐次调用单点更新函数，需要能达到最终结点，时间复杂度为。

线段树提供了延迟更新策略，算是线段树最高光之处。

4.2.4 区间更新

区间更新并不要求一步到位，而是利用了积累的力量。基本思想是边查询边更新，查询到哪里更新到哪里。

如下图所示，线段树上的每一个结点都有一个延迟更新属性，初始值为 。

当需要让区间内所有叶结点值时。更新会延迟到当某次需要查询区间的最大值时，这时从根结点向下查询到结点。让结点 的值增加为 ，且结点 9 的 属性存储增量后再把 返回给根结点，让根结点更新为。

当下次需要查询区间内最大值时。当查询到且发现其属性值不等于。则会把此值向左、右子结点传递。

测试区间更新：

输出结果：可以看到[，当查询到结点时，些结点才一次性全部更新。

5. 总结

线段树是很有个性的数据结构，常用于解决区间类型问题。线段树有一个延迟更新理念，查询深度不同，更新到的深度也不一样。