线段树

本文主要是介绍线段树，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

实现三个功能：
1 add：在l到r区间所有数加一个数
2 update：在l到r区间所有数更新成一个相同的数
3 query：得到l到r区间的和
一般add和update不会同时做，一般一次只需要一个功能。

思路：可以利用二分划分区间，类似多重背包，任何一个数，利用二进制，可以在logn找到它。线段树也是一样，利用二分可实现快速查找。

上图是一个满二叉树，需要2n-1个空间。但如果你的数组长度不是2的指数，其实是无法构成一颗满二叉树的。可能需要补几个元素，让他们为0.
满二叉树：一直一样的范围会分到底，假如是6，会一边有3个，不满足偶数，就会有少分的情况。

所需范围：对于一个任意的n，4n是最多所需的空间。扩充（至多扩充一倍），满二叉树又一倍，所以是四倍。
最不省空间：恰好为2的指数+1，后面需要全部补齐。。

建树及数据结构：数组
只需准备数组，然后保存好hash关系即可。

找孩子：从最大的范围开始，左孩子：2i，右孩子：2i+1，从1开始，这样好处理。
位运算：乘2：i << 1，乘2+1: ( i << 2) | 1（由于左移之后一定是偶数，所以or 1就必然+1了）1
任何时候都能通过简单的乘法找到自己的孩子。
这也是为什么要从1开始的原因，如果从0开始，是2i+1和2i+2，不能用位运算加速。

初始化：即使0位置不用，所以创建4*n个就够了，因为也不可能装满的。
如何填充：用递归，要填第一个位置信息，需要2和3位置，填好后回来填1，分割可以用右移操作，由于都是偶数，可以直接取整。如果两边下标相等，就把数组对应的数填入，终止递归。不需要用记忆化，因为范围是完全没有重叠的。

add操作：
参数：L，R，l，r，rt，C
L和R是要add的区间，l和r是每次递归到子区间的小范围，rt是对应的小区间的sum和lazy数组的索引。C是要add的数。
懒节点更新：卡死区间后在lazy数组存对应的数，复杂度是 O ( l o g n ) O(logn) O(logn)的，这个不严格证明了，感觉一下。
如果大区间lazy后，新的小区间任务又add了，怎么办？把懒信息发给儿子们，直到对应的子区间。
如果发一个信息，所有数组都收到，就是 O ( N ) O(N) O(N)了，因为节点很多。
add是一个递归操作，若L和R能覆盖当前区域，直接更新lazy数组和sum数组，然后return，无需继续下发。否则继续下发任务。用右移划分区间，继续往下更新。递归调用add前，要对lazy和sum数组进行下发，lazy值可以由孩子直接继承，但sum数组需要lazy值乘孩子个数。
如何下发？首先从中间劈开，此时两边都是没处理的。此时lazy和sum数组已经传递到了两边，用L和R和mid比较，如果两边有覆盖的范围，需要继续细分，让lazy数组传递到底。
更新完成后，自己的信息由左孩子和右孩子的sum值累加。
.
例子：让1-2加5，1-2先加5，然后返回给1-4，让1-4的sum更新
当lazy是0时，不往下传递sum和lazy值

例子2：
此时进行第4个任务，要下发lazy和sum，同时反向传播
下发：1-2的lazy值更新为7，sum值增加2*lazy = 4。还要继续更新就不说了，值得注意的是，此时是不需要反向传播的。lazy=0时反向传播是有效的，因为sum不会分发。

update：
引言：如果update了一个范围，那会取消之前所有的lazy。
输入：L，R，l，r，C，rt
update数组是懒更新操作。
如果被包围了，update[rt] = true，当此位置为真是，change数组才有意义。change[rt] = C，直接更新并计算sum，lazy[rt] = 0，然后return。
如果躲不掉，就要下发，方式和之前的一样，但分发函数有所变化。
如果父孩子有懒更新操作，直接更新所有孩子，清空所有lazy，更新所有update和change，直接更新所有sum，父节点的懒更新变为false。
然后，重要的是，if判断完update，还有判断是否lazy。是有可能同时攒着lazy和update，但是lazy时间更靠后。如果update和lazy同时有，lazy肯定是后面来的，否则会被清空，所以按照add中分发方法再发一次。

query:
参数如上
如果全包了，返回sum值
如果不包含，首先pushdown，把update和add下发给后续节点，再进行累加操作。
之后递归的下发query任务，和之前的思想是一样的。

这篇关于线段树的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！