Lazy! 谈区间修改线段树中懒惰标记的设计

一个支持区间修改的线段树, 就要用到lazy标记. 用到哪一个结点, 有效数据就更新到哪一个结点, 避免浪费更新那些不必要的结点的时间. 从根部向下找一个结点, 一路下来根据lazy的设定进行相关的更新操作, 就能快速完成任务. 但是一不小心, 自己临时设定的lazy定义配上临时写出来的代码, 就很有可能有隐蔽的漏洞不被发现.

一个错误的例子

设线段树的数据保存在 segtree[] 里, 懒惰标记保存在 seglazy[] 里.
如果一个结点 lazy = -1, 表示该节点的 segtree 值有效, 其区间修改对lazy的影响已经传给了他的左右儿子.
如果一个结点 lazy != -1, 表示该节点表示的区间内, 所有元素的值都应该被修改为 lazy, 这个信号仍然没有传递给他的左右儿子

对于这个定义, PushDown() 函数这么写:

void PushDown(int l, int r, int rt) {           // 把本节点的lazy下放到子节点
        if (seglazy[rt] == -1)
                return;
        seglazy[rt << 1] = seglazy[rt];
        seglazy[rt << 1 | 1] = seglazy[rt];
        segtree[rt] = seglazy[rt] * (r - l + 1);
        seglazy[rt] = -1;
}

上面这个函数将一个有 lazy 标记(值不为-1) 的结点转化为没有lazy标记, 将lazy传递给他的两个孩子.

再看区间修改函数(高亮的部分有问题):

void modify(int L, int R, int P, int l, int r, int rt) {  // 将区间[L,R]的每一个元素修改为P
        if (L <= l && r <= R) {
                seglazy[rt] = P;
                PushDown(l, r, rt);             // 让他的父亲在 PushUp 的时候可以获取正确的节点值
        } else {
                PushDown(l, r, rt);
                int m = l + (r-l)/2;
                if (L <= m) modify(L, R, P, lson);
                if (m < R) modify(L, R, P, rson);
                PushUp(rt);
        }
}

这个修改函数分为两部分:

如果当前结点不被修改区间所完全覆盖, 那么转移向左右儿子;
如果当前结点被修改区间完全覆盖, 那么把lazy设置为目标值, 然后PushDown一下传给他的两个儿子. 这里用到了PushDown里面 segtree[rt] = seglazy[rt] * (r – l + 1) 这一句的作用, 让当前节点的segtree值有效, 以便他的父亲, 他的祖父亲, 等等, 递归向上更新的时候, 能够拿到正确的值.

这个设计是有问题的, 我反反复复看了好久才看出来.

设有一个长度为2的区间, 一开始所有的懒惰节点都设置为 – 1, 所有的元素都设置为0, 如下图所示:

然后执行区间修改, 把全段修改为200, 得到下图的情况:

此时我不进行查询, 继续把1号元素设置为0, 得到如下结果:

这时候发现父节点的值为0, 是个错误的结果. 应该是100. 出现这个结果的原因是, 对结点[1,1]进行修改完毕之后, 回溯到[1, 2]结点, [1,2]结点把他的两个儿子的segtree结点里面的值直接拿过来用, 而[2, 2]结点的lazy标记被忽略了, 因此[1,2]计算出了错误的结果. [2, 2]结点的lazy被忽略的原因是在Modify [1, 2]的时候, 涉及到了[1, 1], 因此[1, 1]得到了更新, 但是却没有涉及到[2, 2].

这就是一个设计lazy结点与代码结合产生漏洞的例子, 在回溯的时候用到了某个结点的时候, 那个结点尚未进行lazy的PushDown操作.

简单的解决方法是把Modify函数进行修改, 无论那两个if语句到底有没有执行, 都对他的两个儿子进行PushDown操作. 代码如下:

void modify(int L, int R, int P, int l, int r, int rt) {
        if (L <= l && r <= R) {
                seglazy[rt] = P;
                PushDown(l, r, rt);
        } else {
                PushDown(l, r, rt);
                int m = l + (r-l)/2;
                if (L <= m) modify(L, R, P, lson);
                if (m < R) modify(L, R, P, rson);
                PushDown(lson);
                PushDown(rson);
                PushUp(rt);
        }
}

一个好的设计方案

总结上面设计的缺陷, 对lazy进行如下定义

只要递归访问到了一个结点, 无论这个结点的lazy标记是什么, 这个结点的segtree值一定是正确的;
只要对一个结点进行PushDown, 这个结点的左右儿子的segtree值一定是正确的.

于是得到如下代码

void PushDown(int l, int r, int rt) {           // 把本节点的lazy下放到子节点
        if (seglazy[rt] == -1)
                return;
        seglazy[rt << 1] = seglazy[rt << 1 | 1] = seglazy[rt];
        int m = l + (r-l)/2;
        segtree[rt << 1] = seglazy[rt] * (m - l + 1);
        segtree[rt << 1 | 1] = seglazy[rt] * (r - m);
        seglazy[rt] = -1;
}

void modify(int L, int R, int P, int l, int r, int rt) {
        if (L <= l && r <= R) {
                seglazy[rt] = P;
                segtree[rt] = seglazy[rt] * (r - l + 1);
        } else {
                PushDown(l, r, rt);
                int m = l + (r-l)/2;
                if (L <= m) modify(L, R, P, lson);
                if (m < R) modify(L, R, P, rson);
                PushUp(rt);
        }
}

本文链接

一个错误的例子

一个好的设计方案

回复