数据结构详解——文艺线段树

发布于 2017-04-10  315 次阅读


Warning


由于本博客作者实在是太弱啦,本篇文章可能存在大量的错误,漏洞,不规范,不合法之处。若您发现本文章所存在的任何问题,请您尽快在评论区指出,十分感谢!

另外,本文随意转载,但请注明出处。

回顾


上一讲 中,我们解决了线段树的单点修改,区间更新问题。但在文章的最后,普通线段树并不能解决新的问题:

给定一个长为 n 的序列 A,有 m 次操作。

  • add l r p 给从 A[l] 到 A[r] 增加 p
  • ask l r 询问从 lr 的区间和

n,m≤105

文艺线段树


观察这个问题,它与原问题的唯一区别就在于修改范围由点变成一个区间,我们考虑区间修改与点修改有什么区别呢?

单点修改的操作步骤是这样的:从根节点出发,递归找到叶子节点,回溯更新父亲节点。对于区间修改,如果我们暴力套用这个步骤,很明显,时间复杂度是不能接受的,所以我们考虑简化这个步骤:(再次祭出这张图,图源见水印)

假设我们需要修改的区间是 [3,7],比起一步步找到 5 个叶子节点,显然分别更新 [3,4],[5,6],[7,7] 就能完成本次修改,然而,单独更新这几个节点是不够的,事实上,它们的子节点,[3,3],[4,4],[5,5],[6,6] 也需要修改,但若我们递归到这些节点,复杂度就不能保证了。所以矛盾点就在于明明可以只更新部分节点就可以“确定”本次修改,为了满足查询操作的需要,我们不得不一次次地更新,每次更新到底。

等等,真的需要每次都更新到底吗?对于题目给出的操作,“区间加法”,是具有“可累加性”的。(感性理解引号中的词语) 也就是说,进行一次 [3,4] 的+2 操作,[1,2] 的+1 操作,其实等价于进行一次 [1,4] 的+1 操作,一次 [3,4] 的+1 操作。这个性质为我们提供了思路,并非每一次更新都需要更新到底。我们只需要更新到这个区间被“确定”,然后在此记录一个更新值的标记,表明这里尚未更新完毕,在下一次更新时,如果我们不得不走到一个带有更新标记的节点的子节点,我们就“带着这个标记更新”,将标记传递下去。这样,每次更新的递归次数被大大简化,O(nlog n) 的优美时间复杂度就又可以被保证啦!

如何理解这个更新标记呢?习惯地,这个标记我们用数组 lazy 表示,lazy[x] 表示在节点 x 上的目前标记。所以该标记又名懒惰标记,按照普通线段树的想法,对于每次更新,我们应该很勤劳的更新到叶子节点,但在文艺线段树中,我们比较懒惰,除非需要我们更新下去,否则我们是不会更新的,更新的信息就利用 lazy 数组储存在节点上。

实现


理解起来是不困难的,写起来也很容易,对于更新标记,一个新的数组就可以解决,需要注意的是,依旧需要开四倍空间,具体证明在普通线段树的链接中给出。

然而在以上的思考中,我们发现,我们需要引入一个新的函数,用来将父亲节点的信息推入儿子节点,我们用 pushdown 表示。

对于其它函数,我们只有细微的调节,具体可以看代码,注释写的比较清楚了。

pushup 函数是不变的

update 函数需要传递更多的信息

query 函数如下

下面给出可以运行的完整代码

这样,一棵支持区间修改,区间查询的文艺线段树就写出来啦!

例题


想不到很多裸题,bzoj 上的话这道题可以检验对于线段树的理解程度,但可能对初学者来说有一定难度

BZOJ 3212  模版题

BZOJ 1798  题解:(未完成)


一个非常弱的准退役OIER