线段树
线段树是什么?
线段树是一种能让你代码强行增加50行的极容易爆炸的万金油数据结构,用于优雅暴力地解决对一个区间上满足区间可加性(即可由两个子区间的信息得到当前区间信息) 的 区间修改和区间查询问题。
结构:
将区间划分为左端点到中点(即左子区间)和中点+1到右端点(即右子区间)的两个子区间,然后对两个子区间继续划分,直到划分到单个元素(即左端点=右端点)
示意图:
不难看出线段树除了最下面一层,其他的部分一定是一颗完全二叉树,这意味着整棵树可以使用“父子二倍法”(左儿子编号为父亲编号 $\times$ 2,右儿子编号为父亲编号 $\times$ 2 $+$ 1)存储在一个数组中。同时,因为还要考虑到最后一层,数组的大小应开到n $\times$ 4大小。
线段树的一个很重要的性质就是一棵[1~n]的线段树的深度最大为 $log_2 n+1$,这也意味着线段树可在$O(logn)$的时间复杂度内完成所有操作。
实现
以洛谷P3372 【模板】线段树 1的维护最大值为例
首先,我们给线段树中每个元素一个sum变量存储该元素代表区间的区间和,叶子结点的sum是原数组当前位置的值,非叶节点的sum是其左右子节点sum的和,如当原数组为
时,对应的线段树为
节点结构体:
1 |
|
操作
操作有递归和非递归两种形式,递归式相对于非递归式更直观,因此这里讲解递归式。
非递归式和递归式本同末异,考试时按照数据规模而定。
建树:
按照之前提到的定义,从根节点([1~n])向左右两边递归,递归到叶子结点就将该节点sum设为其在原数组中对应的值,回溯时将当前节点的sum设为其左右子节点sum的和。
代码:
1 |
|
复杂度为$O(nlogn)$
区间查询:
设查询区间的左端点为 $l$,右端点为 $r$,当前区间的左端点为 $l_1$,右端点为 $r_1$,中点为$mid$ ,则
- 当 $l \leq l_1$ 且 $r \geq r_1$时 直接返回当前区间的sum,因为当前区间已经涵盖了子区间的全部信息。
- 当 $l \leq mid$时,向左递归,$r_1=mid$(此时查询区间一定涵盖左子区间的一部分)
- 当 $r > mid$时,向右递归,$l_1=mid+1$ (此时查询区间一定涵盖右子区间的一部分)
代码:
1 |
|
复杂度为$O(logn)$
区间修改与延迟标记:
当进行区间修改时,我们依然可以设查询区间的左端点为 $l$,右端点为 $r$,当前区间的左端点为 $l_1$,右端点为 $r_1$,中点为$mid$,同时查询操作也满足这两条性质:
- 当 $l \leq mid$时,向左递归,$r_1=mid$(此时查询区间一定涵盖左子区间的一部分)
- 当 $r > mid$时,向右递归,$l_1=mid+1$ (此时查询区间一定涵盖右子区间的一部分)
但当出现完全覆盖的情况时,事情就变得不那么简单了,一个一个深入更新会使单次修改的复杂度高达 $O(n)$,这是我们所无法接受的。这时,我们就要引入延迟标记。
试想一下,如果你花费很大的代价更新了节点p的子树,但在之后的查询中却根本没有访问到它们,那更新p的子树岂不是白费力气?因此,我们可以在区间修改出现“完全覆盖”情况时也直接返回,但要给当前节点打上一个代表“当前节点已被更新,但其子节点尚未被更新”的延迟标记(这里取名add)。(如果操作是相容的(如加法),那在打标记前无需下传原来的标记。如果操作是不相容的(如赋值),那在打标记前需下传原来的标记。)
在以后的查询操作中,如果遇到了有延迟标记的节点,便将其的两个子节点更新并打上延迟标记,并擦除当前节点的延迟标记(即将延迟标记下传一层),这样就减少了大量无用的更新操作 (虽然本质上依旧是暴力)。
代码:
1 |
|
复杂度为$O(logn)$