线段树

对于较大数据范围内的区间修改、染色、查询问题,单纯的\(N^2\)操作会导致程序超时.

本着用空间换时间的想法,我们可以用一种神奇的数据结构来解决这个问题.

原理

由于二叉树的性质,左右节点与父节点的关系满足如下矩形:

节点 编号
父节点 o
左儿子 o*2
右儿子 o*2+1

所以我们就可以通过建立二叉树,在二叉树上实现查找求和修改染色问题.


遍历一颗二叉树.

这样似乎可以吧.嘤嘤嘤

我们可以用其父亲节点的值来总结叶子节点.

也就是写的pushup的操作

这个维护的区间和,也可以拿来维护区间加减乘除,区间最小最大值.

当然难度不一.打标记大法好啊


首先我们需要建树

上面二叉树的性质有一个小小的限制,就是必须是满二叉树才会有这些性质,如果是一颗歪脖子树或者是一条链是不存在这种操作的.

同时,因为是二叉树,每一个叶子节点到达的方法是唯一的,或者说是到达每一个叶子节点的父亲节点的路径是唯一的.

所以不会重复搜到.


单点修改


单点查询


区间查询


区间修改


也是线段树可以实现一次操作,\(O(log_2n)\)的复杂度的核心之处.

我们每次查找的时间取决于二叉树的高度,所以就是\(O(log_2N)\),q组数据所以总的时间复杂度为\(O(qlog_2n)\)


延迟标记下传是线段树中比较重要的一个部分.

标记下传是对应区间修改的.单点修改的时间复杂度是\(O(log_2n)\)的,但是如果要修改区间\(l-r\)的话,用单点修改的方式,所需要的极限时间复杂度为\(O(nlog_2n)\)的

这样就导致了其总时间复杂度上升为\(O(N^2log_2n)\)的

本末倒置,增加代码难度以及消耗时间反而上升.

类似于上面的程序对于算法竞赛而言并没有什么好处可言.


对于修改区间,是因为他每次修改完单点的之后都会遍历这棵树.保证其更新到叶子节点.

我们就针对这个情况对这个操作进行修改.

因为在同一层的所有操作完了以后再去搞下一层的,可以省下一个\(O(n)\)的复杂度.

所以我们记录一个lazy标记.

如果我们的pushup是总结左右节点的和的话

线段树区间修改就可以改成如第二行那样.

我们让lazy记录的需要修改的值,lazy[o]存储值是说明这个点向下还有需要下传元素的操作.

tr[o]+=val*(r-l)+1的意思就是o节点若不为叶子节点,那么一定总结了其子树的值.子树需要增加的总量就直接更新到父亲节点,这样就可以避免在update完了之后再pushup的操作了.

至于为什么是乘\(r-l+1\),是因为这个节点下叶子节点的个数就是\(r-l+1\)

这样做完的话就是pushdown较为复杂


pushdown

就是当有标记的时候才往下做.那么乘\(M-l+1\)和\(r-M\)与上面的\(r-l+1\)是一个道理.

父亲节点的标记已经下传,那么左右节点接受了这个标记就需要记录,父亲节点的任务已经完成就可以清空了.

与之类似的还有树状数组挖坑

当然这个的强化版就是可持久化.

可持久化是真的不会啊!!

可持久化真的难

其实是我还没学过…


By:Wahacer

2017.12.4

16:54

发表评论

电子邮件地址不会被公开。 必填项已用*标注