线段树二

我们发现对于单点修改的操作每次操作是O(logn)的,若需要直接套到区间修改那样复杂度显然可以达到O(nlogn),因此我们的修改就无法直接修改每一个需要修改的结点,但是我们发现了一件事情,
就是不过我们进行的区间修改/单点修改的操作 这两种操作对于查询操作影响不大,
而且我们可以想一下为什么查询操作,进行单点查询和区间查询都能保证复杂度的,因此我们也可以仿照区间查询来修改,首先比如我们查询区间[4,10],我们会递归到红色的这些结点.而我们并不需要继续往下递归
区间
同样,若我们对区间[4,10]的值全部加上一个val,我们要是也仅仅遍历到红色的区域那样的操作就好了.
但是这样就会有一个问题,我们进行之后的其他操作的时候那样就会导致部分区间的答案不是想要的答案
区间修改
首先我们要进行红色区间修改的最后情况一定是要把或者是能把当前操作遍历到上面所有有颜色的区域的
那样我们先考虑黄色因为我们修改了红色只需要在递归回去的过程中不断执行羡慕的代码,那样就很好的维护黄色的区域,
tr[k].val = tr[k * 2].val + tr[k * 2 + 1].val
PS:这个颜色就是青绿色画图软件的颜色是这样告诉我的
现在我们想要到红色区域停止,这一步也是很容易实现的,因此我们只需要考虑一下青绿色部分怎么修改
我们可以显然的得到一个结论,只要我们把黄色和红色结点维护好,如果不查找到青绿色区域,那怕青绿色区域的值是乱码都没有事情,哪怕我这次修改操作覆盖到这个区域只要不查询到内部就完全没有关系
因此我们就需要引入一个东西'lazy'标记,懒标记,我们发现我们只需要在红色部分打上一个懒标记,给他说,你的孩子们还需要加上一个val值就好,至少在区间加里面lazy标记是这个意思,
lazy标记
但是一般来说的问题我们肯定会遍历到深蓝色甚至是最下面的青绿色因此
1 当我们遍历到红色结点
2 并且发现我们还需要向下遍历的时候
我们先把之前的标记传给他的两个孩子

void pushdown(int k) // 更新了一下函数名,函数名不该叫updete的
{
    if(k结点的lazy标记不为0)
    {
        k的左儿子结点的val值加上 lazy * 左儿子结点的长度
        k的右儿子结点的val值加上 lazy * 右儿子结点的长度
        k的左儿子的lazy标记加上 k的k的azy标记的值
        k的右儿子的lazy标记加上 k的k的azy标记的值
        k的lazy标记清空
    }
}

我们仔细看上面的代码,发现lazy标记就相当于是一个传话筒当我们发现需要取修改或者需要查询有lazy标记的下面的结点,那样lazy标记的用途就是告诉他的孩子两件事情
1. 你的所有儿子要加上val所以你的val值应该加上 你的长度乘上val值
2. 你也要告诉你的孩子,你的值也要加上val(左右儿子lazy+父亲的lazy值)
当然做完这两部操作lazy标记的值就应该清空了
所以说单点修改的线段树和区间修改的线段树是基本上差不了太多的
只需要记得在该往下传递lazy标记的时候一定要下传,在该结束的时候就直接结束,并且要合理修改lazy标记的值

点赞

发表评论

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