【数据结构】线段树【数据结构】线段树

【数据结构】线段树老规矩， Makedown 兼容性差。附上 CSDN 的【数据结构】线段树
问题最后一次用到线段树，是在深圳老东家实习面试的时候，Jason 问到我的一个问题（具体问题不记得了，大致意思）：

一个固定大小 n 的有限数组 x

action 1 : 可以随时更新某个区间 [i, j] 内的元素

action 2 : 可以查询某个区间 [i, j] 内的最大值或最小值

你应该如何做？
简单的解法 1 ？
普通数组形式存储，额外空间消耗，总共空间复杂度.
action 1 : 遍历区间[i, j]，进行元素的更新，时间复杂度.
action 2: 遍历区间 [i, j]，查找最大值或最小值，时间复杂度.
显然这种形式对于有大量查询操作的情况下，耗时会很严重。
这时可以采用线段树进行处理。
线段树时间复杂度和空间复杂度
【【数据结构】线段树】需要预处理生成线段树。
预处理耗时：
总共空间复杂度：
区间更新时间复杂度：
区间查询时间复杂度：
创建线段树
线段树采用二叉树形式存储：

叶子节点对应原始数组 x 中的元素。

非叶子节点表示它所有子孙叶子节点所在区间的最值。

假设数组 x 为：x = [ 2, 5, 1, 4, 9, 3 ] ，一共 n=6 个元素。
那么需要构建的线段树：

graph TD; A(区间 0-5 min: 1)-->B; A-->C; B(区间 0-2 min: 1)-->D; B-->E((1)); C(区间 3-5 min: 3)-->F; C-->G((3)); D(区间 0-1 min: 2)-->H((2)); D-->I((5)); F(区间 3-4 min: 4)-->J((4)); F-->K((9));

注意构建的时候，在非叶子节点更新你想要存储的区间信息（区间最大值，区间最小值等）。
区间查询
查询 [1, 4] 内的最小值

第一步：找到区间范围内的最下层节点：

graph TD; A(区间 0-5 min: 1)-->B; A-->C; B(区间 0-2 min: 1)-->D; B-->E((1 *)); C(区间 3-5 min: 3)-->F; C-->G((3)); D(区间 0-1 min: 2)-->H((2)); D-->I((5 *)); F(区间 3-4 min: 4 *)-->J((4)); F-->K((9));

图中标记 * 号的节点为当前需要查询的节点。
为什么查询的最下层是节点？而不是叶子节点？（请注意看 [3, 4] 区间，不需要查询其叶子节点）
按道理每个区间范围内的叶子节点都需要更新。

线段树每个节点管理的都是一个区间（叶子节点管理的区间内只有一个元素）

我们知道每个划分出来的区间的最小值

如果区间查询的范围 [i, j] 完全包含其中一个区间 [ik, jk]（i <= ik <= jk <= j）

显然这个区间 [ik, jk] 的最小值就是当前值

无需再继续往下查询

[1, 4] 区间包含的节点是：1-1, 2-2, 3-4。

第二步：递归向上查询最小值

对应的最小值分别为：x[1,1]=5, x[2,2]=1, x[3,4]=4
从上到下查找的过程（递归）示例，用 xij 表示区间 x[i, j] 的值：

min(x14) = min(x12, x34) = min(min(x11, x22), 4) = min(min(5, 1), 4) = min(1, 4) = 1

区间更新
更新 [1, 4] 之间所有元素加 3。

第一步：找到需要更新的最下层节点

graph TD; A(区间 0-5 min: 1)-->B; A-->C; B(区间 0-2 min: 1)-->D; B-->E((1 *)); C(区间 3-5 min: 3)-->F; C-->G((3)); D(区间 0-1 min: 2)-->H((2)); D-->I((5 *)); F(区间 3-4 min: 4 *)-->J((4)); F-->K((9));

图中标记 * 号的节点为当前需要更新的节点。
范围同上。
同理：

我们知道每个区间的最小值

如果区间更新的范围 [i, j] 完全包含其中一个区间 [ik, jk]（i <= ik <= jk <= j）

显然这个区间 [ik, jk] 的最小值就是当前值 + 变更值

无须继续向下更新

第二部：递归向上更新区间

递归往上更新后的结果为：

graph TD; A(区间 0-5 min: 2 *)-->B; A-->C; B(区间 0-2 min: 2 *)-->D; B-->E((4 *)); C(区间 3-5 min: 3 *)-->F; C-->G((3)); D(区间 0-1 min: 2 *)-->H((2)); D-->I((8 *)); F(区间 3-4 min: 7 #)-->J((4)); F-->K((9));

图中标记 * 或 # 号的节点为更新过程中需要更新最小值的节点。
等等，是不是有点不对劲？
还是 [3, 4] 这区间。[3, 4] 完全处于 [1, 4] 的更新范围内，在更新时无需更新其所有子节点。
但是按照上图的结果，如果我进行查询 [3, 3] 的最小值（或者更新值）。显然结果与图示的数据不符合。
所以需要增加更新标志位，处理上面所提及的情况。

graph TD; A(区间 0-5 min: 2)-->B; A-->C; B(区间 0-2 min: 2)-->D; B-->E((4)); C(区间 3-5 min: 3)-->F; C-->G((3)); D(区间 0-1 min: 2)-->H((2)); D-->I((8)); F(区间 3-4 min: 7 # +3)-->J((4)); F-->K((9));

该标志位记录当前区间的变更值。
在进行涉及该区间的子节点查询 / 更新时，需要取出该值递归更新沿途的区间。
查询 [3, 3]

graph TD; A(区间 0-5 min: 2)-->B; A-->C; B(区间 0-2 min: 2)-->D; B-->E((4)); C(区间 3-5 min: 3)-->F; C-->G((3)); D(区间 0-1 min: 2)-->H((2)); D-->I((8)); F(区间 3-4 min: 7 # 0)-->J((7 *)); F-->K((12 # +3));

其中 * 号为更新后的值，# 号为传递的标志位。
在更新了区间后，需要把原有的 [3, 4] 标志位清除（否则下次会导致重复更新）。
区间 [4, 5] 所有元素 -2
在查询 [3, 3] 进行这一步操作

graph TD; A(区间 0-5 min: 2)-->B; A-->C; B(区间 0-2 min: 2)-->D; B-->E((4)); C(区间 3-5 min: 3)-->F; C-->G((3 *)); D(区间 0-1 min: 2)-->H((2)); D-->I((8)); F(区间 3-4 min: 7 # +3)-->J((4)); F-->K((9 *));

其中 * 号的为需要更新的最底层节点。

graph TD; A(区间 0-5 min: 2)-->B; A-->C; B(区间 0-2 min: 2)-->D; B-->E((4)); C(区间 3-5 min: 3)-->F; C-->G((3 -2 *)); D(区间 0-1 min: 2)-->H((2)); D-->I((8)); F(区间 3-4 min: 7 # 0)-->J((7 # +3)); F-->K((9 +3-2 *));

把区间标志位和变更值一起传递（注意区间范围），同时清除已经更新完的区间标志位。
结果：

graph TD; A(区间 0-5 min: 1)-->B; A-->C; B(区间 0-2 min: 2)-->D; B-->E((4)); C(区间 3-5 min: 1)-->F; C-->G((1)); D(区间 0-1 min: 2)-->H((2)); D-->I((8)); F(区间 3-4 min: 7)-->J((7)); F-->K((10));