InoueMoby's Blog

前言

上一篇的线段树只支持单点修改。但如果要”把区间 $[3, 7]$ 的所有值都加上 5”呢？逐个修改 5 个点，每次 $O(\log n)$ ，总共 $O(n \log n)$ ——这还不如直接遍历。

懒标记线段树（Lazy Segment Tree）优雅地解决了这个问题。它的核心思想是：不要急着更新所有节点，先”记账”，等需要的时候再”结账”。

就像一个懒惰的管理员：老板说”把 3 楼到 7 楼的灯都打开”，他不会马上跑 5 层楼，而是在笔记本上记一笔”3~7 楼需要开灯”。等有人问”4 楼灯开了没？“的时候，他才去处理。这就是 Lazy Propagation。

问题的本质

为什么需要懒标记？

朴素线段树做区间修改需要 $O(n)$ 时间，因为一个修改可能影响 $O(n)$ 个节点。但如果把修改信息暂时存在内部节点上，查询时才往下推（propagate），每次只推 $\log n$ 层，均摊 $O(\log n)$ 。

关键洞察：一次区间修改只涉及 $O(\log n)$ 个”关键节点”。懒标记只存在这些关键节点上。查询经过时才把标记推给子节点。

标记的合成

如果节点上已经有一个标记”加 3”，现在又要”加 5”，怎么办？直接合成：标记变成”加 8”。这就是标记的可合并性。

更复杂的标记（比如”先乘 $b$ 再加 $c$ “）也需要定义合成规则。这就是仿射变换 (Affine Transformation) 标记。

理论 + 代码

区间加 + 区间求和

每个节点存储：

tree[node]：该区间的和
lazy[node]：待下推的加法值

long long tree[4*MAXN], lazy[4*MAXN];

// ① 下推懒标记
void push(int node, int lo, int hi) {
    if (lazy[node] != 0) {
        int mid = (lo + hi) / 2;
        tree[2*node]   += lazy[node] * (mid - lo + 1); // ② 左子节点加上懒值*区间长
        tree[2*node+1] += lazy[node] * (hi - mid);     // ③ 右子节点同理
        lazy[2*node]   += lazy[node];                   // ④ 懒标记传给左子
        lazy[2*node+1] += lazy[node];                   // ⑤ 懒标记传给右子
        lazy[node] = 0;                                 // ⑥ 清除自己的标记
    }
}

// 区间加
void rangeAdd(int node, int lo, int hi, int ql, int qr, long long val) {
    if (qr < lo || hi < ql) return;           // 不交
    if (ql <= lo && hi <= qr) {
        tree[node] += val * (hi - lo + 1);    // ⑦ 直接更新当前节点
        lazy[node] += val;                     // ⑧ 打上懒标记
        return;
    }
    push(node, lo, hi);                        // ⑨ 查询前先下推
    int mid = (lo + hi) / 2;
    rangeAdd(2*node, lo, mid, ql, qr, val);
    rangeAdd(2*node+1, mid+1, hi, ql, qr, val);
    tree[node] = tree[2*node] + tree[2*node+1]; // ⑩ 合并
}

// 区间求和（和普通线段树一样，只是要先 push）
long long rangeSum(int node, int lo, int hi, int ql, int qr) {
    if (qr < lo || hi < ql) return 0;
    if (ql <= lo && hi <= qr) return tree[node];
    push(node, lo, hi);
    int mid = (lo + hi) / 2;
    return rangeSum(2*node, lo, mid, ql, qr) + rangeSum(2*node+1, mid+1, hi, ql, qr);
}

关键理解：

②③ 为什么是 lazy * length？因为懒标记代表”区间内每个元素都加 lazy”，所以区间和增加了 lazy × 区间长度。
⑦⑧ 遇到完全覆盖的区间，直接更新该节点的值和标记，不往下推——这就是”懒”。
⑨ 只有需要访问子节点时才下推标记。

模拟走一遍

数组 [0,0,0,0,0]，执行 rangeAdd(1,5,3)（位置 1~5 各加 3），然后 rangeSum(2,4)：

步骤	操作	tree[node]	lazy[node]	说明
1	rangeAdd [1,5] +3	tree[1]=15	lazy[1]=3	根节点完全覆盖，打标
2	rangeSum [2,4]			需要进入子节点
3	push根	tree[2]=9,tree[3]=6	lazy[2]=3,lazy[3]=3	标记下推
4	继续查询			递归到完全覆盖的节点

例题

例题 1：T90 029 — Long Bricks（★5）

题目： $W$ 列格子的地面，初始高度全 0。依次放 $N$ 块砖，第 $i$ 块覆盖第 $L_i$ 到 $R_i$ 列。砖放在覆盖范围内最高的水平面上。求每块砖放完后顶面的高度。

数据范围： $2 \le W \le 5 \times 10^5$ ， $1 \le N \le 2.5 \times 10^5$

—— AtCoder Typical 90 029

分析：每块砖的高度 = 区间 $[L_i, R_i]$ 的当前最大值 + 1。然后该区间全部更新为新高度。需要线段树支持区间查询 max + 区间赋值。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 2000006;
int tree[MAXN], lazy[MAXN];

void push(int node) {
    if (lazy[node]) {
        tree[2*node] = max(tree[2*node], lazy[node]);
        tree[2*node+1] = max(tree[2*node+1], lazy[node]);
        lazy[2*node] = max(lazy[2*node], lazy[node]);
        lazy[2*node+1] = max(lazy[2*node+1], lazy[node]);
        lazy[node] = 0;
    }
}

// 区间查询 max
int queryMax(int node, int lo, int hi, int ql, int qr) {
    if (qr < lo || hi < ql) return 0;
    if (ql <= lo && hi <= qr) return tree[node];
    push(node);
    int mid = (lo + hi) / 2;
    return max(queryMax(2*node, lo, mid, ql, qr),
               queryMax(2*node+1, mid+1, hi, ql, qr));
}

// 区间赋值为 max（当前值, val）
void rangeChmax(int node, int lo, int hi, int ql, int qr, int val) {
    if (qr < lo || hi < ql) return;
    if (ql <= lo && hi <= qr) {
        tree[node] = max(tree[node], val);
        lazy[node] = max(lazy[node], val);
        return;
    }
    push(node);
    int mid = (lo + hi) / 2;
    rangeChmax(2*node, lo, mid, ql, qr, val);
    rangeChmax(2*node+1, mid+1, hi, ql, qr, val);
    tree[node] = max(tree[2*node], tree[2*node+1]);
}

int main() {
    int W, N;
    scanf("%d%d", &W, &N);
    while (N--) {
        int L, R;
        scanf("%d%d", &L, &R);
        int h = queryMax(1, 1, W, L, R) + 1; // ① 查询区间最大高度 +1
        rangeChmax(1, 1, W, L, R, h);         // ② 区间更新为新高度
        printf("%d\n", h);
    }
    return 0;
}

逐行解析：

① 查询 $[L, R]$ 的当前最大高度。砖放在这个高度上面，所以新高度 = 最大高度 + 1。
② 把区间 $[L, R]$ 的高度更新为新高度。用 max 赋值——如果某列已经更高（被其他砖覆盖了），不会被降低。

验证： $W=100$ ，砖 [27,100],[8,39],[83,97],[24,75]。高度依次为 1, 2, 2, 3。✓

例题 2：ACL Practice K — Range Affine Range Sum

题目：长度 $N$ 的数组，模 998244353。 $Q$ 个查询：

0 l r b c：对每个 $l \le i < r$ ， $a_i = b \times a_i + c$

1 l r：输出 $\sum_{i=l}^{r-1} a_i \bmod 998244353$

数据范围： $1 \le N, Q \le 5 \times 10^5$

—— AtCoder ACL Practice K

分析：标记是仿射变换 $(b, c)$ ，表示”先乘 $b$ 再加 $c$ “。关键在于标记的合成规则：

新标记 $(b_2, c_2)$ 作用在旧标记 $(b_1, c_1)$ 上 $= (b_2 b_1,\; b_2 c_1 + c_2)$
标记 $(b, c)$ 作用在区间和 $s$ （长度 $\text{len}$ ）上 $\to b \cdot s + c \cdot \text{len}$

代码：

#include <cstdio>
using namespace std;

typedef long long ll;
const ll MOD = 998244353;
const int MAXN = 2000006;

ll sum[4*MAXN], lb[4*MAXN], lc[4*MAXN]; // 区间和、lazy_b、lazy_c
int len_arr[4*MAXN];

void build(int node, int lo, int hi) {
    lb[node] = 1; lc[node] = 0; // ① 默认标记：不变
    len_arr[node] = hi - lo + 1;
    if (lo == hi) { scanf("%lld", &sum[node]); return; }
    int mid = (lo + hi) / 2;
    build(2*node, lo, mid);
    build(2*node+1, mid+1, hi);
    sum[node] = (sum[2*node] + sum[2*node+1]) % MOD;
}

void apply(int node, ll b, ll c) { // ② 对节点施加仿射变换 (b, c)
    sum[node] = (b * sum[node] + c * len_arr[node]) % MOD;
    lb[node] = (b * lb[node]) % MOD;          // ③ 合成 lazy_b
    lc[node] = (b * lc[node] + c) % MOD;      // ④ 合成 lazy_c
}

void push(int node) {
    if (lb[node] != 1 || lc[node] != 0) {
        apply(2*node, lb[node], lc[node]);     // ⑤ 下推左子
        apply(2*node+1, lb[node], lc[node]);   // ⑥ 下推右子
        lb[node] = 1; lc[node] = 0;            // ⑦ 清除标记
    }
}

void rangeAffine(int node, int lo, int hi, int ql, int qr, ll b, ll c) {
    if (qr < lo || hi < ql) return;
    if (ql <= lo && hi <= qr) { apply(node, b, c); return; }
    push(node);
    int mid = (lo + hi) / 2;
    rangeAffine(2*node, lo, mid, ql, qr, b, c);
    rangeAffine(2*node+1, mid+1, hi, ql, qr, b, c);
    sum[node] = (sum[2*node] + sum[2*node+1]) % MOD;
}

ll rangeSum(int node, int lo, int hi, int ql, int qr) {
    if (qr < lo || hi < ql) return 0;
    if (ql <= lo && hi <= qr) return sum[node];
    push(node);
    int mid = (lo + hi) / 2;
    return (rangeSum(2*node, lo, mid, ql, qr) + rangeSum(2*node+1, mid+1, hi, ql, qr)) % MOD;
}

int main() {
    int N, Q;
    scanf("%d%d", &N, &Q);
    build(1, 0, N-1);  // ⑧ 0-indexed
    while (Q--) {
        int t; scanf("%d", &t);
        if (t == 0) {
            int l, r; ll b, c;
            scanf("%d%d%lld%lld", &l, &r, &b, &c);
            rangeAffine(1, 0, N-1, l, r-1, b, c); // ⑨ [l, r)
        } else {
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%lld\n", rangeSum(1, 0, N-1, l, r-1));
        }
    }
    return 0;
}

逐行解析：

① 默认标记 $(b=1, c=0)$ 表示”不修改”（ $1 \cdot x + 0 = x$ ）。
② apply 是懒标记的核心：把仿射变换 $(b, c)$ 作用到节点上。区间和 $\to b \cdot s + c \cdot \text{len}$ 。
③④ 标记合成：新标记 $(b, c)$ 作用在旧标记 $(b_1, c_1)$ 上，结果是 $(b \cdot b_1,\; b \cdot c_1 + c)$ 。
⑤⑥⑦ push 把懒标记下推给子节点，然后清除自己的标记。
⑧ 0-indexed，查询区间是 $[l, r)$ 。
⑨ rangeAffine(1, 0, N-1, l, r-1, b, c) 对 $[l, r-1]$ 施加仿射变换。

例题 3：ACL Practice L — Lazy Segment Tree

题目：01 数组 $A$ 。 $Q$ 个查询：

1 L R：翻转 $[L, R]$ 中的每个元素（0↔1）

2 L R：输出 $A_L, \ldots, A_R$ 的逆序对数

数据范围： $1 \le N, Q \le 2 \times 10^5$

—— AtCoder ACL Practice L

分析：01 数组的逆序对 $= \sum_{i<j, A_i=1, A_j=0} 1$ 。翻转操作是异或标记。

每个节点存储：区间中 1 的个数 cnt1、区间长度 len、区间内部逆序对数 inv、懒标记 flip。合并时跨区间逆序对 = 左子中 1 的个数 $\times$ 右子中 0 的个数。

代码：

#include <cstdio>
using namespace std;

typedef long long ll;
const int MAXN = 800006;

int cnt1[MAXN], len2[MAXN];
ll inv2[MAXN];
bool flip2[MAXN];

void build(int node, int lo, int hi) {
    len2[node] = hi - lo + 1;
    flip2[node] = false;
    if (lo == hi) {
        int a; scanf("%d", &a);
        cnt1[node] = a; inv2[node] = 0;
        return;
    }
    int mid = (lo + hi) / 2;
    build(2*node, lo, mid);
    build(2*node+1, mid+1, hi);
    cnt1[node] = cnt1[2*node] + cnt1[2*node+1];
    inv2[node] = inv2[2*node] + inv2[2*node+1]
              + (ll)cnt1[2*node] * (len2[2*node+1] - cnt1[2*node+1]); // ① 左1×右0
}

void applyFlip(int node) { // ② 翻转
    cnt1[node] = len2[node] - cnt1[node];
    inv2[node] = (ll)len2[node] * (len2[node]-1) / 2 - inv2[node]; // ③ 逆序对↔顺序对
    flip2[node] = !flip2[node];
}

void push(int node) {
    if (flip2[node]) {
        applyFlip(2*node);
        applyFlip(2*node+1);
        flip2[node] = false;
    }
}

void rangeFlip(int node, int lo, int hi, int ql, int qr) {
    if (qr < lo || hi < ql) return;
    if (ql <= lo && hi <= qr) { applyFlip(node); return; }
    push(node);
    int mid = (lo + hi) / 2;
    rangeFlip(2*node, lo, mid, ql, qr);
    rangeFlip(2*node+1, mid+1, hi, ql, qr);
    cnt1[node] = cnt1[2*node] + cnt1[2*node+1];
    inv2[node] = inv2[2*node] + inv2[2*node+1]
              + (ll)cnt1[2*node] * (len2[2*node+1] - cnt1[2*node+1]);
}

ll queryInv(int node, int lo, int hi, int ql, int qr) {
    if (qr < lo || hi < ql) return 0;
    if (ql <= lo && hi <= qr) return inv2[node];
    push(node);
    int mid = (lo + hi) / 2;
    return queryInv(2*node, lo, mid, ql, qr) + queryInv(2*node+1, mid+1, hi, ql, qr);
}

int main() {
    int N, Q;
    scanf("%d%d", &N, &Q);
    build(1, 1, N);
    while (Q--) {
        int T, L, R;
        scanf("%d%d%d", &T, &L, &R);
        if (T == 1) rangeFlip(1, 1, N, L, R);
        else printf("%lld\n", queryInv(1, 1, N, L, R));
    }
    return 0;
}

逐行解析：

① 合并时，跨区间的逆序对 = 左子中 1 的个数 $\times$ 右子中 0 的个数。因为只有 0 和 1，逆序只发生在”左 1 右 0”的情况。
② 翻转：1 变 0，0 变 1。所以 cnt1 = len - cnt1。
③ 翻转后逆序对变顺序对，反之亦然。总对数 $= C_{len}^2 = \frac{len(len-1)}{2}$ ，所以新逆序对 = 总对数 - 旧逆序对。

参考文献

教材讲解 — 競技プログラミングの鉄則

第 8 章 A58 RMQ 讲解线段树基础；懒标记扩展为课堂延伸内容，教材本体 8.8 节之后涉及
8.8 B58 Jumping（线段树优化 DP 解说）

实战练习 — 競プロ典型 90 問

029 Long Bricks（★5，区间 max 更新）【例题】

模板练习 — ACL Practice Contest

系列索引

第零章基础工具

第一章搜索技术

第二章数学基础

第三章数据结构

第四章图论

第五章动态规划

第六章贪心

第七章字符串

第八章进阶

懒标记线段树

如果修改的不是一点而是一整段呢？——延迟更新的艺术

前言

问题的本质

为什么需要懒标记？

标记的合成

理论 + 代码

区间加 + 区间求和

模拟走一遍

例题

例题 1：T90 029 — Long Bricks（★5）

例题 2：ACL Practice K — Range Affine Range Sum

例题 3：ACL Practice L — Lazy Segment Tree

参考文献

系列索引

懒标记线段树