浅谈线段树懒标记

在 线段树基础理论 中，每个节点保存对应区间的摘要 Info。

单点修改只需要沿一条根到叶子的路径更新，但如果一次修改覆盖整个区间，仍然递归到所有叶子再逐层恢复摘要，就又退回了接近暴力修改的复杂度。

懒标记正是为了让这类修改停在当前节点。完整覆盖节点时，先直接更新当前节点的摘要，并记录尚未向子节点传播的操作；只有后续需要进入子树时，才把这段操作继续下传。

一、一次修改为什么可以停在当前节点

P3372 线段树 1：当前节点已经能够得到正确答案

Q1

P3372 【模板】线段树 1
给定一个数列，支持区间加与区间和查询。

数据规模：$N,M\le 10^5$。

先只考虑一次完整覆盖当前节点的区间加。

设当前节点维护区间和 sum，对应长度为 len，若整段加 $k$ 后区间和变成 $sum' = sum + k \cdot len$，所以当前节点不需要访问叶子就能得到正确摘要。

而既然只看当前节点的信息就可以得到修改后的正确摘要，那就没必要继续递归到所有叶子节点。

但这样就会出现一个新的问题，它的两个儿子的摘要仍然停留在修改之前，一旦下一次操作只进入其中一个儿子，就必须把之前遗漏的加法补给它们。

所以每个节点需要额外记录一个 add，表示 “当前节点已经执行，但儿子还没有执行的加法”。

▶

懒标记1 - 区间加

void apply_add( int u, ll val ) {
    tr[u].sum += val * len( u );
    tr[u].add += val;
}

void push_down( int u ) {
    if( !tr[u].add ) return;
    apply_add( ls, tr[u].add );
    apply_add( rs, tr[u].add );
    tr[u].add = 0;
}

二、Tag 本质上是一段可以复合的操作

P3373 线段树 2：从修改量到仿射变换

Q2

P3373 【模板】线段树 2
给定一个数列，支持区间乘、区间加与区间和查询，所有结果对模数取模。

数据规模：$N,M\le 10^5$。

在 Q1 后很容易形成一个粗糙的认识：懒标记就是把“还没下传的修改量”记下来。但区间乘与区间加同时存在以后，这种理解就不够了。

对单个元素来说，任意一段 “先乘后加” 的操作，都可以统一写成一个仿射变换 $f(x)=ax+b$。

若旧操作为 $f(x)=ax+b$，后来又执行 $g(x)=cx+d$；那么儿子最后先执行旧操作，后执行新操作：$g \circ f = g(f(x)) = (ca)x + (cb + d)$，所以最终还是可以用一个乘法标记和加法标记来记录。

若把标记记成 (mul, add)，表示变换 $x \mapsto mul \cdot x + add$，那么新操作 (c,d) 接在旧标记 (a,b) 后面时，新的乘法部分为 $ca$，加法部分为 $cb+d$。也就是说，更新旧 add 时必须先乘上新操作的 mul，再加上新操作的 add。

▶

懒标记2 - 区间仿射

void apply( int u, ll mul, ll add ) {
    tr[u].sum = ( tr[u].sum * mul + add * len( u ) ) % mod;
    tr[u].mul = ( tr[u].mul * mul ) % mod;
    tr[u].add = ( tr[u].add * mul + add ) % mod;
}

void push_down( int u ) {
    if( tr[u].mul == 1 && tr[u].add == 0 ) return;
    apply( ls, tr[u].mul, tr[u].add );
    apply( rs, tr[u].mul, tr[u].add );
    tr[u].mul = 1, tr[u].add = 0;
}

摘要

Tag 可以理解成一个函数，而多个 Lazy 操作的合并就是函数复合。操作复合通常有方向，$new\circ old$ 与 $old\circ new$ 不一定相同，所以新旧操作的时间顺序必须固定。

三、不同操作有不同的复合结构

P2574 XOR 的艺术：操作可以互相抵消

Q3

P2574 XOR 的艺术
维护一个 01 串，支持翻转一段区间中的所有字符，并询问区间内一的数量。

数据规模：$n,m\le 2\times 10^5$。

节点保存一的数量 one。长度为 $len$ 的区间整体翻转后，一的数量变成 $len-one$，所以翻转可以直接作用于完整节点。

但是我们不能把 tag 理解为最近一次修改的参数，因为翻转操作 $F$ 满足 $F\circ F=I$，连续两次翻转等于不翻转，所以 tag 之间的复合要用异或来处理。

▶

懒标记3 - 区间翻转

void apply_rev( int u ) {
    tr[u].one = len( u ) - tr[u].one;
    tr[u].rev ^= 1;
}

加法与翻转的代码不同，但它们并不是两个互不相关的模板。

加法使用 +=，是因为连续操作的复合仍是加法；翻转使用 ^=，是因为这个操作自身可逆，执行两次等于单位操作。

P1558 色板游戏：后来的操作可以抹去历史

Q4

P1558 色板游戏
支持把一段色板覆盖成指定颜色，并询问区间出现了多少种颜色。

数据规模：长度和操作数均不超过 $10^5$，颜色不超过 $30$ 种。

本题的信息合并部分已经在 浅谈线段树信息合并 中讨论，这里只看区间覆盖。若旧操作是“覆盖成颜色 $a$”，新操作是“覆盖成颜色 $b$”，最终只需要保留后者。

把完整区间覆盖成颜色 $c$ 后，旧颜色分布已经没有意义，新的摘要直接变成只含 $c$ 的集合。若节点原来欠儿子一次覆盖 $a$，后来又完整覆盖成 $b$，儿子最终只需要执行覆盖 $b$，旧操作会被新操作彻底替换。

▶

懒标记4 - 区间覆盖

void apply_cover( int u, int mask ) {
    tr[u].col = mask;
    tr[u].cov = mask;
}

笔记

P2824 排序 中的二值序列排序也会反复把某段全部覆盖为零或一，使用的是同一种覆盖机制。不过这道题真正重要的是阈值二值化与排序模拟，所以本篇仅作为其复用案例。

四、多种操作共存时，需要规范表示

P1253 扶苏的问题：覆盖与加法不能交换

Q5

P1253 扶苏的问题
维护一个可能含负数的序列，支持区间覆盖、区间加法和区间最大值查询。

数据规模：$n,q\le 10^6$。

Q1 说明单一操作只需要研究自身复合，而 Q2 的仿射变换已经表明，不同的操作同时存在后，必须考虑复合顺序。

而本题中覆盖与加法的性质差异很大，如何复合呢？若原值为 $x$，先覆盖成 $a$ 再加 $b$，最终得到 $a+b$；先加 $b$ 再覆盖成 $a$，最终只剩 $a$。换而言之，新操作必须接在旧待执行操作之后，真正需要保存的是 new ∘ old，而不是任意交换两个标记。

于是就有一个自然的规范表示：“可选覆盖，再接一次加法”。如果发生覆盖时，旧历史信息全部失效；若是后来发生加法时，则把增量接在后面，所以 push_down 也必须先覆盖、再加法。

▶

懒标记5 - 区间覆盖/区间加

void apply_add( int u, ll val ) {
    tr[u].mx += val;
    tr[u].add += val;
}

void apply_cov( int u, ll val ) {
    tr[u].mx = val;
    tr[u].cov = val;
    tr[u].add = 0;
}

void push_down( int u ) {
    if( tr[u].cov != inf ) {
        apply_cov( ls, tr[u].cov );
        apply_cov( rs, tr[u].cov );
        tr[u].cov = inf;
    }
    if( tr[u].add ) {
        apply_add( ls, tr[u].add );
        apply_add( rs, tr[u].add );
        tr[u].add = 0;
    }
}

P2572 序列操作：把复合关系推到完整阶段

Q6

P2572 序列操作
维护一个 01 序列，支持整段覆盖为零、整段覆盖为一、整体翻转，并查询一的数量和最长连续一段。

数据规模：$n,m\le 10^5$。

这其实很像是前面几题的拼装版：Q3 的区间翻转 + Q5 的懒标记复合，以及 浅谈线段树信息合并 的相关内容。

回到本题，区间和只能回答一的数量，为了合并最长连续段，Info 需要同时维护 $0$ 和 $1$ 各自的最长前缀、后缀与区间答案。

接着为了处理三种修改，Tag 又要表示覆盖零、覆盖一、翻转和单位操作，下面打了个简易的表，若把表中的行看作新操作，列看作节点已有的旧待执行操作，每个格子表示 new ∘ old，四种操作的复合关系如下。

新操作 \ 旧操作	不操作	覆盖零	覆盖一	翻转
不操作	不操作	覆盖零	覆盖一	翻转
覆盖零	覆盖零	覆盖零	覆盖零	覆盖零
覆盖一	覆盖一	覆盖一	覆盖一	覆盖一
翻转	翻转	覆盖一	覆盖零	不操作

覆盖发生在最后时会抹去所有历史；而翻转发生在最后时，已有覆盖 0 变成覆盖 1，已有覆盖 1 变成覆盖 0，只有原来没有覆盖时才需要异或累计翻转。

▶

懒标记6 - 区间覆盖/翻转

void apply_cover( int u, int val ) {
    tr[u].sum = val ? len( u ) : 0;
    tr[u].lmx[0] = tr[u].rmx[0] = tr[u].mx[0] = val == 0 ? len( u ) : 0;
    tr[u].lmx[1] = tr[u].rmx[1] = tr[u].mx[1] = val == 1 ? len( u ) : 0;
    tr[u].cover = val;
    tr[u].rev = 0;
}

void apply_rev( int u ) {
    tr[u].sum = len( u ) - tr[u].sum;
    swap( tr[u].lmx[0], tr[u].lmx[1] );
    swap( tr[u].rmx[0], tr[u].rmx[1] );
    swap( tr[u].mx[0], tr[u].mx[1] );
    if( tr[u].cover != -1 ) tr[u].cover ^= 1;
    else tr[u].rev ^= 1;
}

打这个表的目的是为了检验表示的封闭性，若是任意旧标记接一个新操作，都能回到这四种状态，就说明当前的表示对操作复合是封闭的。

五、P1471：Info 也必须能整体接受操作

P1471 方差：摘要必须能够整体接受操作

Q7

P1471 方差
维护一个数列，支持区间加，并查询区间平均值与方差。

数据规模：$N,M\le 10^5$。

在 浅谈线段树信息合并 中已经讨论过直接维护平均值与方差的写法，不过更常见的实现是保存一次和 sum1 与平方和 sum2。

由方差公式展开：

$$\begin{aligned} S^{2} &= \frac{1}{n} \sum_{i=1}^{n}(A_i-\bar A)^2 \\ &= \frac{1}{n}\sum_{i=1}^{n}A_i^2-\bar A^2 \end{aligned}$$

所以只需要额外维护一个区间平方和，就可以算出方差了。

区间长度为 $n$，整体增加 $k$ 时，一次和变成 $sum1+nk$，平方和变成 $sum2+2k\cdot sum1+nk^2$。后一个式子依赖修改前的 sum1，所以 apply 必须先更新平方和，再更新一次和。

▶

区间加作用于一次和与平方和

void apply_add( int u, double k ) {
    tr[u].sum2 += 2 * k * tr[u].sum1 + k * k * len( u );
    tr[u].sum1 += k * len( u );
    tr[u].add += k;
}

这说明 Tag 能够复合仍然不够。只有当前摘要能够直接接受整段操作，修改才可以停在这个节点；若已有信息不足，就要先补充能够恢复新摘要的统计量。

六、四个职责怎样配合

一次区间修改能够停在完整覆盖节点，依赖下面四个职责共同保持不变量。

1. apply 负责把一次操作立即作用于当前节点的 Info，同时把这次操作接到节点原有的待执行操作之后。
2. Tag 保存当前节点已经执行、但尚未传给两个儿子的等价操作。
3. compose 负责计算 new ∘ old，将多次操作压成固定大小的一个 Tag。
4. push_down 把父节点已经压缩好的 Tag 分别 apply 到两个儿子，再把父节点恢复为单位操作。

apply 既更新摘要，也更新待执行操作：若只改 Info，部分查询进入儿子时会读到旧值；若只改 Tag，完整区间查询又会 WA。

push_down 只负责传播已经确定的操作关系，不能猜测标记优先级。覆盖、加法与翻转的先后次序应当在设计 Tag 和 compose 时就已经推导清楚。

七、普通 Lazy 从哪里失效

P4145 花神游历各国：操作无法直接作用于摘要

Q8

P4145 花神游历各国
支持把区间内每个数替换为平方根下取整，并查询区间和。

假设节点只保存区间和，那么开方操作并不对这个摘要封闭。区间 $4,9$ 与 $1,12$ 的和都为 $13$，但逐项开方后的和分别为 $5$ 与 $4$，所以仅凭旧 sum 无法确定新 sum。

于是普通 Lazy 在 apply 这一步就已经失败，修改必须继续递归。但这样的线段树不就退化了吗？要你有何用？

接着我们会发现，即便初值达到 $10^{12}$，一个数被有效开方的次数也很少，而 $\sqrt{1}=1$，所以值已经不超过 $1$ 的节点可以直接跳过。

也就是说，我们可以同时维护一个区间最大值，如果区间最大值已经是 $1$ 了，就说明这个区间不需要再执行开方操作了，因为此时操作对答案是不影响的。

后续优化依赖的是元素很快进入稳定状态，而不是把开方改写成某种特殊的 Lazy Tag。

▶

稳定状态剪枝

void upd( int u, int l, int r ) {
    if( tr[u].mx <= 1 ) return;
    if( tr[u].l == tr[u].r ) {
        tr[u].sum = sqrt( tr[u].sum );
        tr[u].mx = tr[u].sum;
        return;
    }
    int mid = ( tr[u].l + tr[u].r ) >> 1;
    if( l <= mid ) upd( ls, l, r );
    if( mid < r ) upd( rs, l, r );
    push_up( u );
}

八、从操作反推 Lazy

遇到新的区间修改时，可以按下面的顺序检查。这个流程的目的，是先判断 Lazy 是否成立，再决定 Tag 应该长什么样。

1. 明确单个元素上的真实操作，以及操作的时间顺序。
2. 检查完整区间能否只根据旧 Info、区间长度和操作参数得到新 Info。
3. 如果不能，尝试给 Info 补充有限信息；仍然不能时，普通 Lazy 不成立。
4. 检查任意旧操作再接一个新操作后，能否压回固定大小的同类 Tag。
5. 固定 compose 的方向，并让 apply、push_down 使用同一种时间语义。
6. 最后检查单位操作、标记初值与清空规则。

摘要

Lazy 的核心不是 “延迟 更新 数据”，而是“延迟 传播 操作”。当前节点先完成真实修改，子节点暂时落后，Tag 则保存这段尚未向下传播的等价操作。