关于线段树的一些笔记

下述的各种名词都是我自己编的,因为实在没找到资料。

无标记型

通常只有只有单点修改操作,无区间修改操作时才用无标记型线段树。

相比于树状数组来说,线段树更加灵活。因为树状数组需要同时满足区间信息加和信息减,而线段树只需要满足区间信息加。举个例子,区间求和是满足的,因为知道区间$[a,b]$和$[a,c]$的区间和就可以求出$[b,c]$的区间和。但是区间求最值是不满足的,因为知道区间$[a,b]$和$[a,c]$的区间最值无法求出$[b,c]$的区间最值。

持久化标记型(可叠加标记)

持久化标记型的线段树,标记永远不会下推,而是在查询时把标记应用到计算结果上。这就需要满足在任意节点查询、修改任意区间$[l,r]$时,均可以实时把标记应用到所查询、维护的内容上。

典例:

区间加、区间求和型线段树。每个节点记录着内容“区间和”,标记“增量”。“区间和”即节点区间的所有元素的总和。“增量”即之前对该节点区间进行过区间加操作,这个节点的“区间和”是最新的,但是这个节点的子节点不是。

当对这个节点实施一次区间求和操作(求区间$[l,r]$的每个元素的总和)时,如果查询区间和节点区间匹配,则直接返回节点记录的“区间和”。否则先在子节点上查询,然后将查询得到的值加上$r-l+1$倍“增量”,就是我们要查询的最终结果。

当对这个节点实施一次区间加操作(给区间$[l,r]$的每个元素加上$c$)时,只要将“区间和”加上$r-l+1$倍$c$,就完成了对“区间和”的维护。接下来再判断操作区间与节点区间是否匹配,若匹配则把标记“增量”加上$c$实现更新标记,若不匹配则继续对子节点进行区间加操作。

换个角度思考一下:我们把操作区间分解成若干个小区间,使得存在相应的节点对应于这些小区间,然后分别对每个小区间进行操作。对于区间求和操作,每个节点上的“区间和”值相对于这棵子树来说是最新的,也就是不考虑它的所有祖先节点的情况下,这个区间的和确实等于这个“区间和”值。那么我们只要把这个“区间和”值再加上它的所有祖先节点上的“增量”标记值之和乘以区间长度,就是这个小区间的区间和。而对于区间加操作,我们分别更新这些节点的“增量”标记,并更新它和它的所有祖先记录的的“区间和”。注意,我们通过递归隐式地实现了区间的分解与操作,而不需要真正的考虑如何将区间分解然后分别操作。

更一般地说:我们把操作区间分解成若干个小区间,使得存在相应的节点对应于这些小区间,然后分别对每个小区间进行操作。对于查询操作,我们对每个小区间求值,结果就等于它所对应节点维护的值应用了它和它的所有祖先的标记以后的最终结果。对于修改操作,我们对每个小区间分别修改,即在它所对应节点打上标记,并更新它和它的所有祖先所维护的内容。

下推标记型(可叠加标记)

下推标记型的线段树,适用于在任意节点操作任意区间$[l,r]$时,无法实时把标记更新到所维护的内容上的情况。这里的标记是可叠加的,也就是说当有先后两个修改操作同时涉及区间$[a,b]$时,两次操作都会影响对$[a,b]$查询的结果。

典例:

区间乘,区间求和型线段树。每个节点记录着内容“区间和”,标记“倍率”。“区间和”即节点区间的所有元素的总和。“倍率”即之前对该节点区间进行过区间乘操作,这个节点的“区间和”是最新的,但是这个节点的子节点不是。

如果我们仍按照上面的思路会发现,在区间乘操作中,无法通过操作的参数来实时更新节点的“区间和”。试想我需要在一个节点区间为$[a,b]$的节点上,进行对$[l,r]$区间乘以$c$的这样一个区间乘操作。“区间和”的增量就是$c-1$倍的$[a,b]$区间和,然而$[a,b]$区间和无法求出来,这就导致上述的无法实时把标记更新到所维护的内容上的情况。

不能直接更新?我们可以间接通过子节点来更新啊。具体地来说,我们把标记自顶向下传递,直到这个标记可以直接更新到所维护的内容上(也就是操作区间恰好匹配节点区间时),然后再自底向上更新所维护的内容。

仍然换个角度思考:我们把操作区间分解成若干个小区间,使得存在相应的节点对应于这些小区间,然后分别对每个小区间进行操作。操作过程中我们把根到该节点的路径上所有的标记自顶向下全部推到了该节点上,然后再自底向上维护路径上所有节点的内容。路径上的多个标记在下推时会被叠加成为一个标记。当下一次经过这个节点的时候,标记又会再被推到它的子节点。

Author: ssttkkl
Link: https://ssttkkl.github.io/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/2019/12/%E5%85%B3%E4%BA%8E%E7%BA%BF%E6%AE%B5%E6%A0%91%E7%9A%84%E4%B8%80%E4%BA%9B%E7%AC%94%E8%AE%B0/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.