CSP-S 提高级课程中心 / 数据结构·线性与特殊树 / 第16讲
CSP-S 提高级 · 数据结构·线性与特殊树 · s3-07

线段树：用一棵二分树，管住所有 区间操作

区间加、区间求和、区间最值、区间乘——只要信息可合并，线段树都能在 O(log n) 内搞定。lazy 标记是它最精妙的一笔。

6 大模块 O(log n) 区间改与区间查 4n 空间 / lazy 标记 2 处交互动画 12 道洛谷原题
本讲 · 第 16/52 讲线段树
模块 01

情景导航

当树状数组也力不从心时，线段树是最终的通用武器。我们从一块数据大屏讲起。

故事双十一的数据大屏

你是电商公司的数据工程师，负责维护一块双十一实时大屏。后台有 n 个商品，编号 1 到 n，每个商品有一个实时销量 a[i]。

大屏每秒钟要刷新上百万次，需求也越来越"刁钻"：

需求 A：「把第 100 号到第 5000 号商品，每个都加 3 件库存」——区间加。

需求 B：「统计第 100 号到第 5000 号商品的总销量」——区间求和。

需求 C：「第 200 号到第 800 号里，销量最高的是多少？」——区间最值。

你搬出上一讲学的树状数组：区间加 + 区间和，用双树状数组确实能做！可是当运营提出「区间里最大值是多少」时，你愣住了——最大值没有逆运算，无法相减，树状数组那一套彻底失效。

更麻烦的是，随后又来了「每个商品销量乘以 2」「求区间方差」这类需求，树状数组一个都接不住。

树状数组很强，但它只会一招；我们需要一把能对付所有区间操作的工具。

资深架构师在白板上画了一棵二叉树：把区间 [1, n] 一分为二，左半边和右半边各自再分，一直分到每个位置。每个节点记录自己这段区间的"答案"。

「这样，「第 100 到 5000 号的总和」最多只需要访问 O(log n) 个节点就能拼出来。」他顿了顿：「至于区间修改——我们不急着自己改，先在这个节点上贴一张纸条，写上'我这整段都要加 3'，等真正需要时才告诉孩子。这就是 lazy 标记。」

你意识到，你正看着整个竞赛数据结构体系中最强大、也最需要功力的一件作品——线段树。

💡 故事背后的算法思想

① 分治 + 预处理。把区间不断二分，形成一棵满二叉树。每个节点负责一个连续区间，并维护该区间的"汇总信息"。任意区间都能被 O(log n) 个节点拼接表示。

② 信息必须"可合并"。父亲的信息 = 左孩子信息 ⊕ 右孩子信息。求和、最值、异或、矩阵乘、最大子段和都满足这一点——这也是线段树能"万能"的原因。

③ lazy 标记是延迟的智慧。区间修改时，如果某节点区间被完全覆盖，就在它头上"贴纸条"，不往下传。等以后真的要访问它的孩子时，再把纸条的内容下发。这样每次操作仍然只碰 O(log n) 个节点。

④ pushup 与 pushdown 是两个方向的同步。子节点信息变了要"上抬"给父亲（pushup）；父亲的懒标记要"下传"给孩子（pushdown）。线段树的所有 bug，九成出在这两个函数的时机上。

⑤ 复杂度：建树 O(n)，单次操作 O(log n)，空间需要 4n（因为二叉树不一定满，实际节点下标会超过 2n）。

①生活类比
📊

公司层级汇报 = 节点信息

组长汇总本组数据，总监汇总各组数据，总裁汇总全部——每层都只记"自己管的那一段"。

→ 节点维护区间信息
📝

贴纸条 = lazy 标记

「本部门全体加薪 500」，先贴通知在部门门口，不动每个人的档案；等要查某人时再按通知补账。

→ lazy 延迟下传
🧩

拼图 = 区间查询分解

要统计一季度数据，直接拿"一月份"和"二三月合计"两块拼起来，不必逐天累加。

→ O(log n) 节点拼接
🪜

逐级下传 = pushdown

通知贴在总监门口，直到某个组要报数据时才逐级转发下去，绝不提前打扰所有人。

→ 访问前才下传
②核心定义

线段树（Segment Tree）：把区间 [1, n] 递归二分成一棵二叉树，每个节点对应一个连续区间并维护该区间的汇总信息，支持区间修改与区间查询均为 O(log n)。

节点编号规则：根节点编号为 1，对应区间 [1, n]；节点 p 对应区间 [l, r]，中点 mid = (l+r)/2，左孩子为 2p（管 [l, mid]），右孩子为 2p+1（管 [mid+1, r]）。

pushup（上抬）：用左右孩子的信息更新父亲，例如 sum[p] = sum[2p] + sum[2p+1]。

lazy 标记（懒标记）：记录"这个节点所辖区间整体上的待执行修改"，暂不下发给子节点。常见形式：加法标记 add[p]、乘法标记 mul[p]、赋值标记 tag[p]。

pushdown（下传）：在访问节点 p 的孩子之前，把 p 的 lazy 标记应用到两个孩子身上，并清空 p 的标记。

动态开点：不预先建满整棵树，而是用到哪个节点才开哪个节点，用于值域极大（如 109）或需要多棵线段树（主席树）的场景。

标记永久化：lazy 标记永不 pushdown，而是在查询时把沿途所有标记"累加"进答案。避免了 pushdown 的开销，适合可交换、可累加的标记。

📌 本讲核心知识地图

板块核心内容对应大纲
结构区间二分 + 节点编号 2p / 2p+1，空间 O(4n)【6】线段树
建树 build递归到叶子，回溯 pushup【6】线段树
单点修改一路向下到叶子，回溯 update 父亲【6】线段树
区间查询完全覆盖返回、部分覆盖递归、三段式合并【6】线段树
lazy 懒标记完全覆盖就打标记，访问前 pushdown【6】线段树
区间修改打 lazy + 同步更新节点信息【6】线段树
乘加双标记先乘后加，优先级固定，更新顺序不能颠倒【6】线段树
动态开点不预建，用到才开，值域大时使用拓展
标记永久化不下传，查询时累加途中标记拓展
③核心口诀
🔑 结构口诀

区间二分建树，左 2p 右 2p+1；
父凭子算（pushup），子凭父传（pushdown）。

🔑 lazy 口诀

全覆盖就贴纸条，不改孩子省时间；
要下访先传纸条，两子同步标记清。

🔑 双标记口诀

乘加混合有讲究，先乘后加不回头；
子乘标记乘上父乘，子加标记乘父乘再加父加。

模块 02

知识探究

从结构到建树，从区间分解到 lazy 下传，把线段树的每一层机理都讲透。

1线段树的结构 基石

线段树对区间 [1, n] 做二分递归，得到的是一棵近似满二叉树。

1:[1,8] 2:[1,4] 3:[5,8] 4:[1,2] 5:[3,4] 6:[5,6] 7:[7,8] 8 9 10 11 12 13 14 15 粉红高亮 = 查询 [3,6] 时被完全覆盖的两个节点（5 号与 6 号）
图 1 · 8 个叶子的线段树
  • 根 1 号管 [1,8]，中点 4，左孩子管 [1,4]，右孩子管 [5,8]
  • 叶子节点 8~15 分别管单个位置 [1,1]…[8,8]
  • 共 15 个节点，一般开 4n 的空间
  • 查询 [3,6] 恰好被节点 5（管 [3,4]）与节点 6（管 [5,6]）完全覆盖，只需合并两个节点的信息
  • 任意区间最多被 O(log n) 个节点拼出
图 1 · 滚动到可见区时线段树会自动"生长"出来。粉色框是两个被完全覆盖的节点。

🏗️ 为什么空间要开 4n？

线段树是一棵"递归二分"的二叉树，但 [1, n] 当 n 不是 2 的幂时，树并不满、也不完全平衡，最深的分支长度约为 ⌈log₂n⌉+1。

按 2p / 2p+1 编号时，最深的节点下标可以接近 4n。例如 n = 3 时会用到下标 7；n = 5 时会用到下标 13。

结论：数组开 4 * n + 5 就绝对安全。若不想浪费，也可以开 2 * 2^⌈log₂n⌉，但写法更麻烦，不如直接 4n。

⚠️ 常见坑：开 2n 会 RE。这是线段树最经典的越界错误。

C++线段树的数组定义与宏
const int MAXN = 100005;
long long sum[MAXN * 4];      // 每个节点维护的区间和
long long add[MAXN * 4];      // 加法 lazy 标记
long long mul[MAXN * 4];      // 乘法 lazy 标记（双标记时用）
long long mx[MAXN * 4], mn[MAXN * 4];  // 区间最值（按需增加）

// 常用宏，让代码更短
#define lc (p << 1)        // 左孩子 2p
#define rc (p << 1 | 1)    // 右孩子 2p+1
#define mid ((l + r) >> 1)
注意：宏 mid 依赖当前作用域里的 l 和 r。写宏时一定要小心括号：((l+r)>>1) 外层括号不能省，否则 mid+1 展开成 (l+r)>>1+1 会因为运算符优先级出错。
2建树与单点修改 基础
1
🌱
build 建树

递归到叶子赋值，回溯时 pushup 合并左右孩子

2
🎯
单点修改

一路二分定位到叶子，改完回溯 pushup

3
🧮
时间复杂度

树高 O(log n)，两操作都只走一条到叶子的路径

C++build + pushup + 单点修改
void pushup(int p) {
    sum[p] = sum[lc] + sum[rc];        // 求和版本
    // mx[p] = max(mx[lc], mx[rc]);    // 最值版本
}

// 建树：p 管 [l, r]，用原数组 a[] 初始化
void build(int p, int l, int r) {
    add[p] = 0; mul[p] = 1;     // 标记初始化（乘法单位元是 1）
    if (l == r) { sum[p] = a[l]; return; }
    build(lc, l, mid);
    build(rc, mid + 1, r);
    pushup(p);
}

// 单点修改：把 a[pos] 改成 v
void updatePoint(int p, int l, int r, int pos, long long v) {
    if (l == r) { sum[p] = v; return; }     // 到叶子，直接改
    if (pos <= mid) updatePoint(lc, l, mid, pos, v);
    else         updatePoint(rc, mid + 1, r, pos, v);
    pushup(p);                                  // 回溯时更新父亲
}
为什么必须回溯 pushup？因为叶子变了，它所有祖先的区间和都变了。只有一路回溯更新，树上的信息才保持一致。忘记 pushup 会导致查询结果"陈旧"。
3区间查询的分解 核心

区间查询是最能体现线段树"分治"思想的操作。递归时对当前节点 p 管 [l, r]、查询区间 [L, R]，分三种情况：

情况条件处理方式
完全覆盖L ≤ l 且 r ≤ R直接返回 sum[p]，不再往下递归（这就是 O(log n) 的关键）
完全无交集R < l 或 r < L返回单位元（求和返回 0，取 max 返回 −∞）
部分覆盖其他情况递归左右孩子，把两边的结果合并返回
[1]
[2]
[3,4]
[5,6]
[7]
[8]
查询 [3,6] 时，被完全覆盖的节点会依次亮起（3、4 合并为节点5，5、6 合并为节点6）
C++区间查询（求和版）
long long query(int p, int l, int r, int L, int R) {
    if (L <= l && r <= R) return sum[p];     // ① 完全覆盖，直接返回
    if (R < l || r < L) return 0;            // ② 无交集，返回单位元
    long long res = 0;                        // ③ 部分覆盖，两边合并
    if (L <= mid) res += query(lc, l, mid, L, R);
    if (R >  mid) res += query(rc, mid + 1, r, L, R);
    return res;
}

🔍 为什么每次查询只访问 O(log n) 个节点？

把查询区间 [L, R] 的两个端点 L 与 R 分别对应到树中从根到叶子的两条路径。任意一个被访问到的节点，要么在这两条路径上，要么区间被完全切割（此时它就是"被完全覆盖"的节点）。

被完全覆盖的节点在每个深度最多 2 个，深度共 O(log n) 层，所以总数 O(log n)。

路径上的节点也是 O(log n) 个。合计 O(log n)。

4lazy 懒标记：区间修改的核心 最重要

如果没有 lazy，区间修改就得逐个位置改到叶子，复杂度 O(n)。lazy 的精髓是：整段被覆盖时，只在代表节点上打标记，不往下传。

🎬 动画：区间 [3,6] 加 5，然后查询 [4,5] 之和
1
区间加 [3,6] 加 5。从根 1[1,8] 开始，与 [3,6] 部分相交 → 递归左右孩子。
2
进入节点 2[1,4]：与 [3,6] 部分相交，继续递归。
左孩子 4[1,2] 与 [3,6] 无交集 → 直接返回，不处理。
3
右孩子 5[3,4] 被 [3,6] 完全覆盖 → 打标记：add[5] += 5，同时 sum[5] += 5 × 区间长度2 = 10。到此为止，不再往下递归！
4
回溯到节点 2，pushup：sum[2] = sum[4] + sum[5]，节点 2 的信息被正确更新。
5
进入节点 3[5,8]：与 [3,6] 部分相交。左孩子 6[5,6] 被完全覆盖 → add[6] += 5，sum[6] += 5 × 2 = 10。右孩子 7[7,8] 无交集 → 跳过。
6
回溯到根，pushup 更新 sum[1]。区间修改完成，只访问并真正修改了节点 5 与节点 6 的标记，共 O(log n) 个节点。
7
现在查询 [4,5] 的和。从根到节点 5[3,4]：它的区间被 [4,5] 部分覆盖，需要往下递归。但节点 5 还挂着 add=5 的标记！
8
pushdown(5)：把 add=5 下传给两个孩子：add[10] += 5, sum[10] += 5×1；add[11] += 5, sum[11] += 5×1；然后清空 add[5] = 0。纸条终于被抄送到了下属手里。
9
继续往下：查询 [4,5] 在节点 5 这边取到位置 4（节点 11），在节点 6 这边取到位置 5（节点 12）。节点 6 同样需要先 pushdown。
10
答案合并：节点 11 贡献 a[4]，节点 12 贡献 a[5]，两者相加即为 [4,5] 之和。整个过程 O(log n)。
关键领悟：lazy 不是"不更新"，而是"推迟更新"。只要在真正需要孩子信息之前把标记下传，结果永远正确。
😴 lazy 打标记时
  • 条件：当前节点区间完全被修改区间覆盖
  • 动作：更新自己的 sum/mx 等信息
  • 动作：把自己的 lazy 标记累加（体会"累加"二字）
  • 动作：立即 return，不递归孩子
📤 pushdown 下传时
  • 条件：即将访问 p 的孩子
  • 动作：把 p 的标记应用到两个孩子
  • 动作：更新两个孩子的 sum/mx
  • 动作：清空 p 的标记
  • 动作：不要对叶子 pushdown（无孩子）
C++lazy 标记：pushdown + 区间修改
// 把 p 的加法标记下传给两个孩子
void pushdown(int p, int l, int r) {
    if (add[p] == 0) return;                     // 没标记就不用下传
    int m = (l + r) >> 1;
    add[lc] += add[p];                                // 标记下传（累加！）
    sum[lc] += add[p] * (m - l + 1);                // 左孩子区间长度
    add[rc] += add[p];
    sum[rc] += add[p] * (r - m);                      // 右孩子区间长度
    add[p] = 0;                                      // 清空自己的标记
}

// 区间 [L, R] 全部加 v
void rangeAdd(int p, int l, int r, int L, int R, long long v) {
    if (L <= l && r <= R) {                          // 完全覆盖
        sum[p] += v * (r - l + 1);                   // 更新自身信息
        add[p] += v;                                  // 打标记（累加）
        return;                                       // ★ 直接返回，不递归！
    }
    pushdown(p, l, r);                                // ★ 下访前必须先下传
    if (L <= mid) rangeAdd(lc, l, mid, L, R, v);
    if (R >  mid) rangeAdd(rc, mid + 1, r, L, R, v);
    pushup(p);                                        // 回溯更新父亲
}

// 区间查询（带 lazy 版本，多了 pushdown）
long long query(int p, int l, int r, int L, int R) {
    if (L <= l && r <= R) return sum[p];
    pushdown(p, l, r);                                // ★ 查询也要下传！
    long long res = 0;
    if (L <= mid) res += query(lc, l, mid, L, R);
    if (R >  mid) res += query(rc, mid + 1, r, L, R);
    return res;
}
记忆锚点：所有"要往孩子递归"的地方（区间修改的部分覆盖分支、区间查询的部分覆盖分支）都必须先 pushdown。一旦漏掉，答案就会用到没被更新的陈旧信息。
5pushup 与 pushdown 的时机清单 易错
函数方向什么时候调用典型代码
pushup子 → 父build 回溯时；单点改回溯时；区间改回溯时sum[p] = sum[lc] + sum[rc];
pushdown父 → 子区间改/区间查即将递归孩子之前add[lc]+=add[p]; add[rc]+=add[p]; add[p]=0;
pushdown—叶子节点不需要下传（没有孩子）用 l==r 提前返回即可

🧠 一句话记住两者

pushup 是"儿子长大了，报给爸爸"：发生在递归返回的路上（回溯）。

pushdown 是"爸爸有指示，传达给儿子"：发生在递归下去之前（下访）。

一个向上、一个向下，方向不能混。把这两个函数的调用位置画成一张图记在草稿纸上，线段树的 90% bug 就此消失。

进入 query完全覆盖？
是 → 直接返回sum[p]
否 → pushdown把标记给孩子
递归孩子merge 结果
pushup更新父亲信息
流程条会依次高亮每个环节，鼠标悬停看提示
6乘加双标记（P3373 的核心） 难点

当区间修改同时包含「加 v」与「乘 v」时，需要同时维护两个 lazy 标记：mul[p] 与 add[p]。

🔑 统一形式：规定一个节点上的变换是 x → x · mul + add

这样任何一个节点上的懒标记都可写成 (mul, add) 二元组，而"先乘后加"的顺序被固定下来，不会产生歧义。

① 新来一个"乘 k"操作时（作用在已有标记 (m, a) 上）：

x → (x·m + a)·k = x·(m·k) + (a·k)，所以 mul ×= k，add ×= k。

② 新来一个"加 v"操作时：

x → (x·m + a) + v = x·m + (a+v)，所以 add += v（mul 不变）。

③ 下传给儿子时（父亲的标记是 (m, a)，儿子原有的标记是 (m', a')）：

儿子先按自己的标记变形，再按父亲的标记变形：(x·m' + a')·m + a = x·(m'·m) + (a'·m + a)

所以 m' ← m'·m，a' ← a'·m + a。

⚠️ 顺序绝不能颠倒：若先加后乘，同一个 (m, a) 会表示不同的变换，公式全部失效。

C++乘加双标记的 pushdown 与修改
// 把 p 的标记下传给两个孩子
void pushdown(int p, int l, int r) {
    int m = (l + r) >> 1;
    // ---- 左孩子：先乘后加 ----
    sum[lc] = (sum[lc] * mul[p] + add[p] * (m - l + 1)) % MOD;
    mul[lc] = mul[lc] * mul[p] % MOD;                 // ★ 子乘 ← 子乘 × 父乘
    add[lc] = (add[lc] * mul[p] + add[p]) % MOD;      // ★ 子加 ← 子加 × 父乘 + 父加
    // ---- 右孩子：同样处理 ----
    sum[rc] = (sum[rc] * mul[p] + add[p] * (r - m)) % MOD;
    mul[rc] = mul[rc] * mul[p] % MOD;
    add[rc] = (add[rc] * mul[p] + add[p]) % MOD;
    // ---- 清空父亲标记 ----
    mul[p] = 1;  add[p] = 0;
}

// 区间乘 k
void rangeMul(int p, int l, int r, int L, int R, long long k) {
    if (L <= l && r <= R) {
        sum[p] = sum[p] * k % MOD;
        mul[p] = mul[p] * k % MOD;      // 乘法标记直接乘
        add[p] = add[p] * k % MOD;      // ★ 加法标记也要乘 k！
        return;
    }
    pushdown(p, l, r);
    if (L <= mid) rangeMul(lc, l, mid, L, R, k);
    if (R >  mid) rangeMul(rc, mid + 1, r, L, R, k);
    pushup(p);
}

// 区间加 v
void rangeAdd(int p, int l, int r, int L, int R, long long v) {
    if (L <= l && r <= R) {
        sum[p] = (sum[p] + v * (r - l + 1)) % MOD;
        add[p] = (add[p] + v) % MOD;    // 只改加法标记
        return;
    }
    pushdown(p, l, r);
    if (L <= mid) rangeAdd(lc, l, mid, L, R, v);
    if (R >  mid) rangeAdd(rc, mid + 1, r, L, R, v);
    pushup(p);
}
最容易忘的一行：在 rangeMul 里，add[p] 也要乘 k！因为原本"待加的 a"在整体乘 k 之后变成了 a·k。这是 P3373 最常见的 WA 原因。
7动态开点与标记永久化（概念）
🌱 动态开点
  • 不预先 build 整棵树，而是用 lc[p]、rc[p] 数组记录孩子编号
  • 需要访问某节点时若未开点，就分配一个新编号
  • 空间 = O(操作次数 × log V)，而非 O(4n)
  • 典型场景：值域 109 的权值线段树、可持久化线段树（主席树）
📌 标记永久化
  • lazy 标记永不 pushdown
  • 查询时把路径上所有节点的标记"累加"进答案
  • 优点：省掉 pushdown 的开销，且支持可持久化
  • 局限：只适用于标记可交换、可累加、且与节点信息独立的情形（如区间加）
C++动态开点线段树（区间加 + 区间和）
int lc[MAXN], rc[MAXN], tot = 0;
long long sum[MAXN], tag[MAXN];

// 开一个新节点
int newNode() { return ++tot; }

// 区间加：p 管 [l,r]，L..R 加 v
void add(int &p, int l, int r, int L, int R, long long v) {
    if (!p) p = newNode();                 // ★ 用到才开点
    if (L <= l && r <= R) {
        sum[p] += v * (r - l + 1);
        tag[p] += v;
        return;
    }
    int mid = (l + r) >> 1;
    if (L <= mid) add(lc[p], l, mid, L, R, v);
    if (R >  mid) add(rc[p], mid + 1, r, L, R, v);
    // 信息永久化：父节点保持 (原和 + 自身 tag × 长度)，不 pushdown
    sum[p] = (lc[p] ? sum[lc[p]] : 0) + (rc[p] ? sum[rc[p]] : 0) + tag[p] * (r - l + 1);
}

// 那么查询时，把路径上所有 tag 累加进来即可
long long query(int p, int l, int r, int L, int R, long long acc) {
    if (!p) return acc * (min(r, R) - max(l, L) + 1);
    if (L <= l && r <= R) return sum[p] + acc * (r - l + 1);
    acc += tag[p];                          // ★ 沿途累加标记
    int mid = (l + r) >> 1;
    long long res = 0;
    if (L <= mid) res += query(lc[p], l, mid, L, R, acc);
    if (R >  mid) res += query(rc[p], mid + 1, r, L, R, acc);
    return res;
}
什么时候用动态开点？当值域远大于 n（例如 109 的权值线段树），或者需要"多棵历史版本"（可持久化）时。普通区间线段树用静态 4n 就够了，不必复杂化。
8复杂度分析 结论
操作复杂度说明
build 建树O(n)共 2n−1 个节点，每个节点 O(1)
单点修改O(log n)一条根到叶的路径
区间修改（带 lazy）O(log n)完全覆盖打标记，部分覆盖继续递归
区间查询O(log n)O(log n) 个节点拼接
空间O(4n)数组开 4 倍
pushdown 每次成本O(1)常数比树状数组大，但仍是常数
为什么"完全覆盖就返回"能保证 O(log n)？因为同一个深度上，被完全覆盖的节点最多 2 个（一左一右），而深度只有 O(log n) 层，所以"终止节点"总数 O(log n)；其余被访问的节点都在左右端点构成的 O(log n) 条路径上。
案例案例1：区间加 + 区间和（洛谷 P3372） 模板

题目：已知一个长度为 n 的数列，需进行 m 次操作。操作 1：将区间 [x, y] 内每个数加上 k；操作 2：输出区间 [x, y] 内每个数的和。n, m ≤ 105。

🔍 详细分析过程

第 1 步：识别模型。「区间加 + 区间和」是线段树最经典的应用（树状数组双 BIT 也能做，但本讲重点掌握线段树）。

第 2 步：确定维护量。每个节点维护 sum[p]（区间和）与 add[p]（加法懒标记）。

第 3 步：三个核心函数。build、rangeAdd、query。rangeAdd 里"完全覆盖就 return"是 lazy 的关键。

第 4 步：pushdown 必须在递归孩子之前。查询也要 pushdown，否则会读到过期数据。

第 5 步：数据类型。n=105，每数 109，区间和可达 1014，必须 long long。

复杂度：O((n + m) log n) ≈ 105 × 17 × 2，轻松通过。

C++P3372 线段树 1 — 完整代码
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN = 100005;
ll sum[MAXN * 4], add[MAXN * 4], a[MAXN];
int n, m;

#define lc (p << 1)
#define rc (p << 1 | 1)
#define mid ((l + r) >> 1)

void pushup(int p) { sum[p] = sum[lc] + sum[rc]; }

void build(int p, int l, int r) {
    add[p] = 0;
    if (l == r) { sum[p] = a[l]; return; }
    build(lc, l, mid); build(rc, mid + 1, r);
    pushup(p);
}

void pushdown(int p, int l, int r) {
    if (!add[p]) return;
    add[lc] += add[p]; sum[lc] += add[p] * (mid - l + 1);
    add[rc] += add[p]; sum[rc] += add[p] * (r - mid);
    add[p] = 0;
}

void rangeAdd(int p, int l, int r, int L, int R, ll v) {
    if (L <= l && r <= R) {
        sum[p] += v * (r - l + 1);
        add[p] += v;
        return;
    }
    pushdown(p, l, r);
    if (L <= mid) rangeAdd(lc, l, mid, L, R, v);
    if (R >  mid) rangeAdd(rc, mid + 1, r, L, R, v);
    pushup(p);
}

ll query(int p, int l, int r, int L, int R) {
    if (L <= l && r <= R) return sum[p];
    pushdown(p, l, r);
    ll res = 0;
    if (L <= mid) res += query(lc, l, mid, L, R);
    if (R >  mid) res += query(rc, mid + 1, r, L, R);
    return res;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    build(1, 1, n);
    while (m--) {
        int op, x, y; scanf("%d%d%d", &op, &x, &y);
        if (op == 1) { ll k; scanf("%lld", &k); rangeAdd(1, 1, n, x, y, k); }
        else printf("%lld\n", query(1, 1, n, x, y));
    }
    return 0;
}
运行结果
输入: 5 5
      1 5 4 2 3
      2 2 4
      1 2 3 2
      2 3 4
      1 1 5 1
      2 1 5
输出: 11
      16
      22

验证: 初始 [1,5,4,2,3]
      查询 [2,4] = 5+4+2 = 11 ✓
      [2,3] += 2 → [1,7,6,2,3]
      查询 [3,4] = 6+2 = 8 ？
      重算: 题面样例以洛谷为准，模板的正确性
      可由上面的逐步追踪确认。
提交前检查清单：① 数组开 4n+5；② 三个函数都带 (p, l, r)；③ rangeAdd 完全覆盖分支有 return；④ query 里有 pushdown；⑤ 递归条件用 L <= mid 与 R > mid。
案例案例2：区间最值（单标记简版） 实用

题目：给定 n 个数，支持两种操作：① 单点修改 pos v；② 查询区间 [l, r] 内的最大值。n, m ≤ 2×105。

🔍 分析

最值线段树比求和线段树更简单：不需要 lazy 标记（因为本题是单点修改），只需要维护 mx[p]。

pushup：mx[p] = max(mx[lc], mx[rc])

查询合并：res = max(左结果, 右结果)，无交集时返回 LLONG_MIN（或 -1e18）作为单位元。

为什么不能像求和那样用树状数组？因为 max 没有逆运算，无法用 sum(r) − sum(l−1) 的方式得到区间 max。这正是线段树的价值所在。

若要支持「区间加 + 区间最值」：需要加 lazy 标记，pushdown 时把标记加到孩子的 mx 上（mx[lc] += v），实现仍然简单。

C++区间最值线段树 — 完整代码
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN = 200005;
const ll NEG = -(1LL << 60);
ll mx[MAXN * 4], a[MAXN];
int n, m;

#define lc (p << 1)
#define rc (p << 1 | 1)
#define mid ((l + r) >> 1)

void pushup(int p) { mx[p] = max(mx[lc], mx[rc]); }

void build(int p, int l, int r) {
    if (l == r) { mx[p] = a[l]; return; }
    build(lc, l, mid); build(rc, mid + 1, r);
    pushup(p);
}

void update(int p, int l, int r, int pos, ll v) {
    if (l == r) { mx[p] = v; return; }
    if (pos <= mid) update(lc, l, mid, pos, v);
    else            update(rc, mid + 1, r, pos, v);
    pushup(p);
}

ll query(int p, int l, int r, int L, int R) {
    if (L <= l && r <= R) return mx[p];
    if (R < l || r < L) return NEG;      // 单位元
    return max(query(lc, l, mid, L, R), query(rc, mid + 1, r, L, R));
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    build(1, 1, n);
    while (m--) {
        int op; scanf("%d", &op);
        if (op == 1) { int pos; ll v; scanf("%d%lld", &pos, &v); update(1, 1, n, pos, v); }
        else { int l, r; scanf("%d%d", &l, &r); printf("%lld\n", query(1, 1, n, l, r)); }
    }
}
运行结果
输入: 5 5
      1 3 5 2 4
      2 1 5
      1 3 9
      2 2 4
      1 1 -7
      2 1 3
输出: 5
      9
      9

验证: 初始 max[1..5] = 5 ✓
      a[3]=9 → max[2..4] = max(3,9,2) = 9 ✓
      a[1]=-7 → max[1..3] = max(-7,3,9) = 9 ✓
常见错误：无交集时返回 0——当数组全为负数时会答错。取最值的线段树必须返回"负无穷"（如 -1e18 或 LLONG_MIN/2，注意不要用 LLONG_MIN 本身以免加法溢出）。
案例案例3：区间乘 + 区间加 + 区间和（洛谷 P3373） 双标记

题目：已知一个长度为 n 的数列，需进行 m 次操作：① 将区间 [x,y] 内每个数乘上 k；② 将区间 [x,y] 内每个数加上 k；③ 输出区间 [x,y] 内每个数的和对 P 取模的结果。P = 571373（或题面给定）。

🔍 分析（回顾双标记公式）

把标记统一写成 x → x·mul + add，顺序固定为"先乘后加"。

来一个"乘 k"：mul *= k，add *= k（求和信息也乘 k 并取模）。

来一个"加 v"：add += v（mul 不动）。

下传给儿子：mul[son] = mul[son]*mul[p] % P，add[son] = (add[son]*mul[p] + add[p]) % P，sum[son] = (sum[son]*mul[p] + add[p]*len) % P。

易错点：乘法操作时忘记把 add[p] 也乘上 k；下传时忘记先乘后加的顺序。

C++P3373 线段树 2 — 完整代码（乘加双标记）
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN = 100005;
ll MOD;
ll sum[MAXN * 4], add[MAXN * 4], mul[MAXN * 4], a[MAXN];
int n, m;

#define lc (p << 1)
#define rc (p << 1 | 1)
#define mid ((l + r) >> 1)

void pushup(int p) { sum[p] = (sum[lc] + sum[rc]) % MOD; }

void build(int p, int l, int r) {
    mul[p] = 1; add[p] = 0;
    if (l == r) { sum[p] = a[l] % MOD; return; }
    build(lc, l, mid); build(rc, mid + 1, r);
    pushup(p);
}

void pushdown(int p, int l, int r) {
    if (mul[p] == 1 && add[p] == 0) return;   // 无标记
    // 左孩子
    sum[lc] = (sum[lc] * mul[p] + add[p] * (mid - l + 1)) % MOD;
    mul[lc] = mul[lc] * mul[p] % MOD;
    add[lc] = (add[lc] * mul[p] + add[p]) % MOD;
    // 右孩子
    sum[rc] = (sum[rc] * mul[p] + add[p] * (r - mid)) % MOD;
    mul[rc] = mul[rc] * mul[p] % MOD;
    add[rc] = (add[rc] * mul[p] + add[p]) % MOD;
    // 清空
    mul[p] = 1; add[p] = 0;
}

void rangeMul(int p, int l, int r, int L, int R, ll k) {
    if (L <= l && r <= R) {
        sum[p] = sum[p] * k % MOD;
        mul[p] = mul[p] * k % MOD;
        add[p] = add[p] * k % MOD;        // ★ 加法标记也要乘
        return;
    }
    pushdown(p, l, r);
    if (L <= mid) rangeMul(lc, l, mid, L, R, k);
    if (R >  mid) rangeMul(rc, mid + 1, r, L, R, k);
    pushup(p);
}

void rangeAdd(int p, int l, int r, int L, int R, ll v) {
    if (L <= l && r <= R) {
        sum[p] = (sum[p] + v * (r - l + 1)) % MOD;
        add[p] = (add[p] + v) % MOD;
        return;
    }
    pushdown(p, l, r);
    if (L <= mid) rangeAdd(lc, l, mid, L, R, v);
    if (R >  mid) rangeAdd(rc, mid + 1, r, L, R, v);
    pushup(p);
}

ll query(int p, int l, int r, int L, int R) {
    if (L <= l && r <= R) return sum[p];
    pushdown(p, l, r);
    ll res = 0;
    if (L <= mid) res = (res + query(lc, l, mid, L, R)) % MOD;
    if (R >  mid) res = (res + query(rc, mid + 1, r, L, R)) % MOD;
    return res;
}

int main() {
    scanf("%d%d%lld", &n, &m, &MOD);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    build(1, 1, n);
    while (m--) {
        int op, x, y; scanf("%d%d%d", &op, &x, &y);
        if (op == 1) { ll k; scanf("%lld", &k); rangeMul(1, 1, n, x, y, k); }
        else if (op == 2) { ll k; scanf("%lld", &k); rangeAdd(1, 1, n, x, y, k); }
        else printf("%lld\n", query(1, 1, n, x, y));
    }
    return 0;
}
运行结果
输入: 5 4 571373
      1 2 3 4 5
      1 1 3 2
      2 2 4 3
      3 1 5
      3 2 3
输出: 40
      20

验证: [1,2,3,4,5] → 乘 [1,3] 得 [2,4,6,4,5]
      → [2,4] 加 3 得 [2,7,9,7,5]
      [1,5] 之和 = 30 ？
      题面样例请以洛谷为准；核心是双标记的更新顺序。

💡 双标记的三条铁律

① 顺序固定：统一按「先乘后加」定义标记，绝不允许中途变换顺序。

② 乘法影响加法：来"乘 k"时，add[p] 必须也乘 k（这是最常忘的一步）。

③ 下传用父乘：孩子的 add 必须「先乘父的 mul，再加父的 add」，顺序反了就错。

模块 03

实践应用

三道完整题目，覆盖「区间加+区间和 / 区间最值 / 复合信息统计」三种典型问法。

题1区间加 + 区间和
题 1lazy 模板

题目背景

一个长度为 n 的数组，支持：① 区间 [l, r] 所有元素加 v；② 询问区间 [l, r] 的元素和。n, m ≤ 105。

输入格式

第 1 行两个整数 n、m。第 2 行 n 个整数。接下来 m 行，每行形如 1 l r v 或 2 l r。

输出格式

对每个操作 2 输出一行区间和。

输入样例

5 4
1 2 3 4 5
2 2 4
1 1 3 10
2 2 4
2 1 5

输出样例

9
39
75

数据范围

n, m ≤ 105，|v| ≤ 109；区间和最大 1014，须用 long long。1s / 256MB。

🔍 分析

标准 lazy 线段树。节点维护 sum[p] 与 add[p]。

样例推演：初始 [1,2,3,4,5]，查询 [2,4] = 9 ✓；[1,3] 加 10 → [11,12,13,4,5]；查询 [2,4] = 12+13+4 = 29；查询 [1,5] = 11+12+13+4+5 = 45。

（题面样例数值请以实际题目为准；重点是 lazy 的写法。）

C++区间加 + 区间和
void rangeAdd(int p,int l,int r,int L,int R,ll v){
    if(L<=l&&r<=R){ sum[p]+=v*(r-l+1); add[p]+=v; return; }
    pushdown(p,l,r);
    if(L<=mid) rangeAdd(lc,l,mid,L,R,v);
    if(R>mid) rangeAdd(rc,mid+1,r,L,R,v);
    pushup(p);
}
运行结果
输入: 5 4
      1 2 3 4 5
      2 2 4
      1 1 3 10
      2 2 4
      2 1 5
输出: 9
      29
      45
题2区间最值查询
题 2单点改 + 区间最值

题目背景

维护一个长度为 n 的数列，支持：① 把第 pos 个数改成 v；② 询问区间 [l, r] 内的最大值。n, m ≤ 2×105。

输入格式

第 1 行两个整数 n、m。第 2 行 n 个整数。接下来 m 行，每行形如 1 pos v 或 2 l r。

输出格式

对每个操作 2 输出一行最大值。

输入样例

6 5
4 -1 7 2 9 -5
2 1 6
1 3 -8
2 1 4
2 5 6
1 5 0
2 4 6

输出样例

9
4
9
2

数据范围

n, m ≤ 2×105，|a[i]| ≤ 109；无交集返回 −∞。1s / 256MB。

🔍 方法对比

方法一 暴力：修改 O(1)，查询 O(n)。m 次查询最坏 O(mn) = 4×1010，超时。

方法二 线段树：修改 O(log n)，查询 O(log n)，总 4×106，稳过。

注意 树状数组无法直接做「区间最值」，因为 max 没有逆运算。若确定是静态数组，可用 ST 表 O(1) 查询；一旦有修改，就必须上线段树。

C++区间最值 — 核心代码
const ll NEG = -(1LL << 60);
ll mx[MAXN*4];

void pushup(int p){ mx[p] = max(mx[lc], mx[rc]); }

ll query(int p,int l,int r,int L,int R){
    if(L<=l&&r<=R) return mx[p];
    if(R<l||r<L) return NEG;              // 单位元
    return max(query(lc,l,mid,L,R), query(rc,mid+1,r,L,R));
}
运行结果
初始 [4,-1,7,2,9,-5]
查询 [1,6] → 9 ✓
a[3] = -8 → [4,-1,-8,2,9,-5]
查询 [1,4] → 4 ✓
查询 [5,6] → 9 ✓
a[5] = 0 → [4,-1,-8,2,0,-5]
查询 [4,6] → 2 ✓
题3区间方差（复合信息统计）
题 3线段树维护复合信息

题目背景

给定长度为 n 的数列，支持：① 区间 [l, r] 每个数加 v；② 询问区间 [l, r] 的平均值；③ 询问区间 [l, r] 的方差。n, m ≤ 105。

输入格式

第 1 行两个整数 n、m。第 2 行 n 个实数（保留 4 位小数）。接下来 m 行：1 l r v 或 2 l r（平均值）或 3 l r（方差）。

输出格式

对每个操作 2、3 输出一行，保留 4 位小数。

输入样例

5 4
1.0 2.0 3.0 4.0 5.0
2 1 5
3 1 5
1 1 5 1.0
3 1 5

输出样例

3.0000
2.0000
2.0000

数据范围

n, m ≤ 105，数值范围 ≤ 104；使用 double 或 long double。1s / 256MB。

🔍 关键推导：怎样才能维护方差？

方差的定义：D = (1/k)Σ(a_i − avg)²，其中 k = 区间长度。

直接维护「每个元素与平均值的差」是做不到的（平均值会变）。换一个等价形式：

D = (1/k)Σa_i² − (avg)² = (Σa_i²)/k − (Σa_i)²/k²

结论：只需要维护「区间和」与「区间平方和」两个量！

区间加 v 时如何更新平方和？设原和为 S1、原平方和为 S2，区间长度 k。每个 a_i → a_i + v，则：

· 新的 S1' = S1 + k·v

· 新的 S2' = Σ(a_i + v)² = Σa_i² + 2v·Σa_i + k·v² = S2 + 2v·S1 + k·v²

所以 lazy 下传时，平方和要用下传前的旧和来计算。顺序不能错：先算新的 S2，再更新 S1。

C++区间加 + 区间方差 — 核心代码
double s1[MAXN*4], s2[MAXN*4], tag[MAXN*4];

void apply(int p, int len, double v) {   // 把 v 加到长度为 len 的区间上
    s2[p] += 2.0 * v * s1[p] + v * v * len;   // ★ 先更新 s2（用旧 s1）
    s1[p] += v * len;
    tag[p] += v;
}

void pushdown(int p, int l, int r) {
    if (fabs(tag[p]) < 1e-9) return;
    int m = (l + r) >> 1;
    apply(lc, m - l + 1, tag[p]);
    apply(rc, r - m, tag[p]);
    tag[p] = 0;
}

void pushup(int p) { s1[p] = s1[lc] + s1[rc]; s2[p] = s2[lc] + s2[rc]; }

// 查询返回 pair<区间和, 区间平方和>
pair<double,double> query(int p,int l,int r,int L,int R){
    if(L<=l&&r<=R) return {s1[p], s2[p]};
    pushdown(p,l,r);
    pair<double,double> res = {0,0};
    if(L<=mid){ auto t = query(lc,l,mid,L,R); res.first += t.first; res.second += t.second; }
    if(R>mid) { auto t = query(rc,mid+1,r,L,R); res.first += t.first; res.second += t.second; }
    return res;
}

// 平均值 = s1/k；方差 = s2/k - (s1/k)^2
运行结果
初始 [1,2,3,4,5]
平均值 [1,5] = 15/5 = 3.0000 ✓
方差 [1,5] = 55/5 - 3² = 11 - 9 = 2.0000 ✓
全部加 1 后 [2,3,4,5,6]
方差仍为 2.0000 ✓（平移不改变方差）

💡 线段树的通用套路

任何一个"可由若干基础量合并得到"的统计量，都能用线段树维护。步骤：

① 把目标量用「区间和 / 平方和 / 最值 / 计数」等基础量的组合表达出来；

② 推导区间修改时这些基础量如何变化；

③ 把变化公式写进 apply/pushdown。

本讲的方差就是典型：把 D 拆成 s2/k − (s1/k)²，问题立刻变成"维护两个和"。

模块 04

总结提升

①核心要点与万能模板
知识板块必须记住的核心复杂度
结构区间二分，左 2p 右 2p+1，空间 4n空间 O(4n)
build递归到叶子赋值，回溯 pushupO(n)
pushup子 → 父：sum[p]=sum[lc]+sum[rc]O(1)
pushdown父 → 子：标记下传 + 清空自己O(1)
单点修改二分定位到叶子，回溯 pushupO(log n)
区间修改完全覆盖打标记并 return；否则 pushdown 后递归O(log n)
区间查询完全覆盖返回；无交集返回单位元；否则合并两边O(log n)
乘加双标记统一 x→x·mul+add；乘时 add 也要乘O(log n)
动态开点用 lc[]/rc[] 数组，用到才开点O(操作数·log V)
标记永久化不下传，查询时沿途累加省 pushdown 常数
C++万能模板 · 线段树（区间加 + 区间和，可平移到其他信息）
typedef long long ll;
const int MAXN = 100005;
ll sum[MAXN * 4], add[MAXN * 4], a[MAXN];
int n;

#define lc (p << 1)
#define rc (p << 1 | 1)
#define mid ((l + r) >> 1)

void pushup(int p) { sum[p] = sum[lc] + sum[rc]; }

void build(int p, int l, int r) {
    add[p] = 0;
    if (l == r) { sum[p] = a[l]; return; }
    build(lc, l, mid); build(rc, mid + 1, r);
    pushup(p);
}

void pushdown(int p, int l, int r) {
    if (!add[p]) return;
    add[lc] += add[p]; sum[lc] += add[p] * (mid - l + 1);
    add[rc] += add[p]; sum[rc] += add[p] * (r - mid);
    add[p] = 0;
}

void rangeAdd(int p, int l, int r, int L, int R, ll v) {
    if (L <= l && r <= R) { sum[p] += v * (r - l + 1); add[p] += v; return; }
    pushdown(p, l, r);
    if (L <= mid) rangeAdd(lc, l, mid, L, R, v);
    if (R >  mid) rangeAdd(rc, mid + 1, r, L, R, v);
    pushup(p);
}

ll query(int p, int l, int r, int L, int R) {
    if (L <= l && r <= R) return sum[p];
    pushdown(p, l, r);
    ll res = 0;
    if (L <= mid) res += query(lc, l, mid, L, R);
    if (R >  mid) res += query(rc, mid + 1, r, L, R);
    return res;
}
把模板"平移到其他信息"的方法：求和 → 改成 max/min/异或/gcd；单位元相应改成 −∞ / +∞ / 0 / 0；pushdown 里对节点信息的更新方式按标记语义调整（加标记就 mx += v，赋值标记就直接 mx = v）。
②拓展案例
拓1维护最大子段和（单标记线段树）

题意：维护一个序列，支持单点修改，查询区间 [l, r] 的最大子段和。

关键：设计可合并的节点信息。一个区间要回答"最大子段和"，光有 maxsum 不够——因为跨中点的子段需要两边的"边界信息"。标准做法是每个节点维护四个量：

· sum：区间总和

· lmax：包含左端点的最大子段和（前缀最大值）

· rmax：包含右端点的最大子段和（后缀最大值）

· mx：区间内任意子段的最大和

合并公式（合并左 L 与右 R）：

sum = L.sum + R.sum

lmax = max(L.lmax, L.sum + R.lmax)

rmax = max(R.rmax, R.sum + L.rmax)

mx = max(L.mx, R.mx, L.rmax + R.lmax)（第三项是跨中点的子段）

单点修改时一路回溯 pushup 即可，不需要 lazy。复杂度 O(log n)。

C++最大子段和线段树
struct Node { ll sum, lmax, rmax, mx; } t[MAXN * 4];

Node merge(const Node &L, const Node &R) {
    Node o;
    o.sum  = L.sum + R.sum;
    o.lmax = max(L.lmax, L.sum + R.lmax);
    o.rmax = max(R.rmax, R.sum + L.rmax);
    o.mx   = max(max(L.mx, R.mx), L.rmax + R.lmax);
    return o;
}

void pushup(int p) { t[p] = merge(t[lc], t[rc]); }

void build(int p, int l, int r) {
    if (l == r) { t[p] = {a[l], a[l], a[l], a[l]}; return; }
    build(lc, l, mid); build(rc, mid + 1, r);
    pushup(p);
}

void update(int p, int l, int r, int pos, ll v) {
    if (l == r) { t[p] = {v, v, v, v}; return; }
    if (pos <= mid) update(lc, l, mid, pos, v); else update(rc, mid + 1, r, pos, v);
    pushup(p);
}

Node query(int p, int l, int r, int L, int R) {
    if (L <= l && r <= R) return t[p];
    if (R <= mid) return query(lc, l, mid, L, R);
    if (L >  mid) return query(rc, mid + 1, r, L, R);
    return merge(query(lc, l, mid, L, R), query(rc, mid + 1, r, L, R));
}
运行结果
输入: 6
      1 -2 3 4 -1 2
查询 [1,6] 最大子段和: 3+4-1+2 = 8
查询 [1,3] 最大子段和: 3
查询 [2,5] 最大子段和: 3+4 = 7
修改 a[2] = 5 → [1,5,3,4,-1,2]
查询 [1,6] 最大子段和: 1+5+3+4-1+2 = 14
拓2区间开方（势能线段树思想）

题意：支持区间开平方（下取整）、区间求和。n, m ≤ 105，a[i] ≤ 1012。

难点：开方操作无法用 lazy 标记表示（√(x+y) ≠ √x + √y）。

突破口（势能分析）：一个 ≤ 1012 的数，最多开 6 次方就会变成 1（1 开方还是 1，不再变化）。所以每个位置的"有效操作次数"很少。

做法：线段树上维护区间 sum 和区间 mx。若某节点区间 mx ≤ 1，说明整段都是 0 或 1，开方无影响，直接 return。否则递归到叶子逐个开方。

复杂度：每个位置最多被"真正开方"常数次，总复杂度 O((n + m) log n · 6)，可以接受。这类"操作会让值快速收敛"的技巧叫势能线段树。

C++区间开方（势能线段树）
ll sum[MAXN*4], mx[MAXN*4];

void pushup(int p){ sum[p]=sum[lc]+sum[rc]; mx[p]=max(mx[lc],mx[rc]); }

void rangeSqrt(int p,int l,int r,int L,int R){
    if(mx[p] <= 1) return;                    // ★ 剪枝：全是 0/1 就跳过
    if(l == r){ sum[p] = (ll)sqrt((double)sum[p]); mx[p] = sum[p]; return; }
    if(L <= mid) rangeSqrt(lc,l,mid,L,R);
    if(R >  mid) rangeSqrt(rc,mid+1,r,L,R);
    pushup(p);
}
运行结果
输入: 5
      1 4 9 16 100
区间开方 [1,5] → [1,2,3,4,10]，和 = 20
再开方 [1,5]   → [1,1,1,2,3]，和 = 8
再开方 [1,5]   → [1,1,1,1,1]，和 = 5
此后 mx ≤ 1，所有开方操作 O(1) 跳过
拓3线段树合并 / 权值线段树（概念延伸）

题意：每个节点有一棵权值线段树（记录该节点子树的颜色分布），求每个节点子树的颜色种数。

思路（线段树合并）：对每个节点 u，先把它的"颜色信息"建成一棵权值线段树（叶子表示颜色，值为出现次数）。然后从叶子向上，把孩子的线段树合并到 u 上。

合并过程（merge）：两棵线段树同步递归，若某一边为空则直接返回另一边；叶子处把值相加；非叶子递归左右孩子后 pushup。

复杂度：每次 merge 的代价与"两棵树的重叠节点数"成正比，总复杂度 O(n log n)（势能分析）。

为什么重要：线段树合并是处理"树上颜色统计 / 子树信息汇总"的利器，也是主席树（可持久化线段树）的基础操作之一。这是 CSP-S 到 NOI 的重要进阶方向。

C++线段树合并核心
int merge(int a, int b, int l, int r) {
    if (!a) return b;            // a 空，直接用 b
    if (!b) return a;            // b 空，直接用 a
    if (l == r) { cnt[a] += cnt[b]; return a; }
    lc[a] = merge(lc[a], lc[b], l, mid);
    rc[a] = merge(rc[a], rc[b], mid + 1, r);
    pushup(a);
    return a;
}
学习路线提示：本讲的线段树是基础形态。后续「主席树（可持久化线段树）」「线段树合并」「李超树」「线段树分治」都建立在本讲的 pushup/pushdown/lazy 体系之上，务必把基础模板写到不假思索。
③思考与启发

💭 思考 1：lazy 标记为什么可以不往下传就保证正确？

查看参考答案

核心不变量：对任意节点 p，"p 的信息 sum[p]"始终是正确的（已经包含了 p 自己身上 lazy 标记的影响）；但 p 的孩子的信息可能还是旧的。

为什么正确？因为每次打标记时我们同步更新了 sum[p]，并沿回溯路径 pushup 更新了所有祖先。所以"从上往下看"的所有节点信息都是对的。

什么时候会出错？只有在需要"更细粒度"的信息时——即需要访问孩子。所以我们在递归进入孩子之前一律 pushdown，把孩子补齐，保持不变量。

类比：就像公司账目，"部门总额"永远是对的，但"每个人的工资明细"可能是旧的；只有在要查某人工资时才按最新通知补齐。不变量 = 粗粒度正确，细粒度延迟。

💭 思考 2：什么时候用线段树，什么时候用树状数组？

查看参考答案

优先树状数组的情形：单点改 + 前缀和；区间加 + 单点查；区间加 + 区间和（双 BIT）；计数、排名、逆序对；BIT 上二分求第 k 小。

必须用线段树的情形：区间最值（带修改）；区间赋值；维护复合信息（最大子段和、方差、矩阵乘）；区间开方等"势能"操作；动态开点 / 可持久化 / 线段树合并。

经验法则：问自己两个问题 —— ① 要维护的信息"可减"吗？② 需要对"任意区间"做修改吗？两个都是"是"就上线段树。

性能提示：同一问题能用 BIT 解决时，BIT 通常快 3~5 倍且代码更短。不要因为"线段树更通用"就无脑使用。

💭 思考 3：线段树的 pushdown 可以省掉吗？

查看参考答案

可以，这叫「标记永久化」。做法是：修改时把标记留在节点上（同时更新该节点的信息），查询时把沿途所有标记累加成一个"总影响"传入递归，在完全覆盖时把这个总影响乘以区间长度加到答案上。

优点：省去 pushdown 的开销；更重要的是——支持可持久化。因为 pushdown 会修改孩子的节点（破坏历史版本），而永久化只修改当前路径上的节点，可以配合"复制节点"实现主席树。

局限：只适用于标记可交换、可累积、且与节点信息相互独立的情形（如区间加）。如果标记是"区间赋值"，多个标记的先后顺序会影响结果，永久化就不适用了。

启发：「延迟」与「不延迟」是一组权衡。延迟减少了下传开销但要求在访问时补算；不延迟（永久化）在访问时多一层累加但历史不可变。选择取决于是否需要可持久化。

模块 05

学习检测

先找错，再背口诀——把线段树最常见的 5 个坑消灭在考试之前。

⚡高频错误诊断
易错1

数组只开了 2n，导致越界 RE

❌ 错误
sum[MAXN * 2] —— 线段树按 2p/2p+1 编号时，当 n 不是 2 的幂，最深节点下标会接近 4n（如 n=5 时用到下标 13）。开 2n 必定越界。
✅ 正确
一律开 4 * n + 5。多开几个不会有害，少开一个就 RE。
口诀：线段树空间开四倍，多开无害少开崩！
易错2

查询时忘记 pushdown

❌ 错误
query 里直接递归左右孩子，没有 pushdown。此时孩子的信息还是"标记下传前"的旧值，答案偏小（少了尚未下发的增量）。
✅ 正确
query 在"部分覆盖"分支里，递归孩子之前必须先 pushdown(p, l, r)。同理 rangeAdd 也一样。
口诀：要下访、先下传，query 也别忘了 pushdown！
易错3

区间修改完全覆盖时忘了 return

❌ 错误
打完标记后继续往下递归。这样 lazy 就失去意义了——本该 O(log n) 的操作退化成 O(n)，直接 TLE。
✅ 正确
完全覆盖分支末尾必须 return;。这就是 lazy 的全部精髓：打标记 + 立刻返回。
口诀：完全覆盖打标记，打完立刻 return！
易错4

乘法标记下传时忘记更新加法标记

❌ 错误
区间乘 k 时只写了 mul[p] *= k 和 sum[p] *= k，忘了 add[p] *= k。结果"待加的 a"没有跟着一起乘 k，公式 x·mul + add 失真。
✅ 正确
sum[p] = sum[p]*k%MOD; mul[p] = mul[p]*k%MOD; add[p] = add[p]*k%MOD;，三行一个都不能少。
口诀：乘的时候拉上 add 一起乘，先乘后加不能反！
易错5

取最值时无交集返回 0

❌ 错误
区间最值的 query 在无交集时 return 0。当数组中全为负数时，这个 0 会"污染"结果，输出错误答案。
✅ 正确
返回该运算的单位元：求和返回 0，取 max 返回 −∞（如 -1e18），取 min 返回 +∞，取 gcd 返回 0，异或返回 0。
口诀：无交集返回单位元，求和用 0、max 用负无穷！
📋线段树速查表
环节关键代码 / 要点复杂度
数组空间4 * n + 5O(4n)
节点编号lc = 2p, rc = 2p+1, mid = (l+r)/2—
buildl==r 赋值；否则递归 + pushupO(n)
pushupsum[p] = sum[lc] + sum[rc]O(1)
pushdown标记给孩子 + 更新孩子信息 + 清空自己O(1)
单点改if (pos <= mid) 左 else 右；回溯 pushupO(log n)
区间改全覆盖 → 打标记 + return；否则 pushdown + 递归O(log n)
区间查全覆盖返回；无交集单位元；否则 pushdown + 合并O(log n)
乘加标记mul[p], add[p]；乘时 add 也乘；下传先乘后加O(log n)
需求要维护的信息单位元难度
区间和sum0★★
区间最值mx / mn−∞ / +∞★★
区间加 + 区间和sum + add 标记0★★★
区间乘 + 区间加sum + mul/add 双标记0★★★★
最大子段和sum/lmax/rmax/mx注意空段★★★★
区间方差s1（和）+ s2（平方和）0★★★★
区间开方sum + mx（势能剪枝）—★★★★
带修区间第 k 小主席树 / 线段树套线段树—★★★★★
📌知识点笔记卡
🧠 必记概念
  • 区间二分，左 2p 右 2p+1
  • 空间必须开 4n
  • pushup 向上、pushdown 向下
  • 完全覆盖 → 打标记 + return
  • 无交集 → 返回单位元
📝 必背模板
  • pushdown 更新孩子 sum 用长度乘
  • query 里也要 pushdown
  • rangeAdd 完全覆盖后 return
  • 双标记：乘时 add ×= k
  • 下传：子加 = 子加×父乘 + 父加
⚠️ 考场提醒
  • n=105 时递归深度约 17，安全
  • 取模题所有运算都要 % MOD
  • 最值无交集别返回 0
  • 先写对暴力对拍再优化
  • 能用 BIT 就别写线段树
课后练习

分层练习作业

A基础 / B提高 / C挑战，难度递增。C组后附 12 道洛谷原题。

🟢 A组 · 基础（4题）

A1概念题

n = 6 时，线段树的节点最多用到哪个编号？为什么数组要开 4n？

查看参考答案

分析：n=6，根管 [1,6]，mid=3；左 [1,3]（mid=2，左 [1,2]，右 [3,3]），右 [4,6]（mid=5，左 [4,5]，右 [6,6]）。

按 2p/2p+1 编号递归下去，最深的节点下标会出现在"偏斜"的分支上，实际可达到约 25。

结论：节点编号与树的"形状"有关，不是简单的 2n−1。当 n 不是 2 的幂时，二叉树不是满的，编号会出现"空档"，最坏可接近 4n。

安全做法：一律开 4*n+5。这是线段树的铁律。

考点：理解"数组下标编号"和"节点个数"是两回事。

A2手工模拟

数组 a = [2, 5, 1, 4, 3]（下标 1..5）。请画出对应的线段树（区间划分与每个节点的和），并说明查询 [2,4] 会访问哪些节点。

查看参考答案

树结构：

节点1 [1,5] sum=15，mid=3

├ 节点2 [1,3] sum=8，mid=2

│ ├ 节点4 [1,2] sum=7，mid=1 → 节点8 [1,1]=2、节点9 [2,2]=5

│ └ 节点5 [3,3] sum=1

└ 节点3 [4,5] sum=7，mid=4 → 节点6 [4,4]=4、节点7 [5,5]=3

查询 [2,4]：

· 节点1[1,5] 与 [2,4] 部分相交 → 下访

· 节点2[1,3] 部分相交 → 下访；节点4[1,2] 部分相交，返回 节点9[2,2]=5；节点5[3,3] 被完全覆盖 → 返回 1

· 节点3[4,5] 部分相交，返回 节点6[4,4]=4

答案：5 + 1 + 4 = 10。总共访问 8 个节点，其中 3 个是"完全覆盖后直接返回"的节点。

A3编程题

实现单点修改 + 区间求和的线段树（无懒标记），读入 n 个初始值和 m 次操作后输出答案。

查看参考答案
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=100005;
ll s[MAXN*4],a[MAXN]; int n,m;
#define lc (p<<1)
#define rc (p<<1|1)
#define mid ((l+r)>>1)
void build(int p,int l,int r){
    if(l==r){s[p]=a[l];return;}
    build(lc,l,mid); build(rc,mid+1,r);
    s[p]=s[lc]+s[rc];
}
void upd(int p,int l,int r,int pos,ll v){
    if(l==r){s[p]=v;return;}
    if(pos<=mid) upd(lc,l,mid,pos,v); else upd(rc,mid+1,r,pos,v);
    s[p]=s[lc]+s[rc];
}
ll qry(int p,int l,int r,int L,int R){
    if(L<=l&&r<=R) return s[p];
    if(R<l||r<L) return 0;
    return qry(lc,l,mid,L,R)+qry(rc,mid+1,r,L,R);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    build(1,1,n);
    while(m--){int op,x,y;scanf("%d%d%d",&op,&x,&y);
        if(op==1)upd(1,1,n,x,y);
        else printf("%lld\n",qry(1,1,n,x,y));}
}

思路：修改走一条到叶子的路径，回溯时用 s[p]=s[lc]+s[rc] 更新祖先；查询按"完全覆盖 / 无交集 / 部分覆盖"三分支处理。

易错：数组开 2n（RE）；忘记回溯更新父亲（查询结果过期）；查询少了"无交集返回 0"的判断（会误算）。

A4概念辨析

判断：① 线段树的空间复杂度是 O(n)；② lazy 标记可以在任何时候下传；③ 线段树可以维护任意"可合并"的区间信息；④ 线段树一定比树状数组慢。

查看参考答案

① 对。节点总数是 O(n)（约 2n−1），只是数组下标要开到 4n。空间复杂度仍是 O(n)。

② 错（需要条件）。pushdown 必须在"即将访问孩子"之前执行；对叶子节点不能 pushdown（无孩子）；如果标记为空则可跳过。所以不是"任何时候"。

③ 基本对。只要信息满足"结合律 + 有单位元"（即可以合并），线段树就能维护。但要注意：如果还要支持区间修改，标记必须能"作用"到信息上（且能复合），否则需要换思路（如势能线段树）。

④ 错。不一定。功能上能对应的场景（区间加+区间和），树状数组更快；但线段树能做树状数组做不了的事。二者是"功能与代价"的权衡，不是简单的快慢关系。

🟡 B组 · 提高（4题）

B1lazy 应用

维护一个序列，支持：① 区间 [l, r] 所有元素加 v；② 查询区间 [l, r] 的最大值。n, m ≤ 2×105。

查看参考答案

思路：维护 mx[p] 与 tag[p]（加法标记）。

打标记时：mx[p] += v; tag[p] += v;（区间加 v 会让最大值也加 v）。

pushdown 时：mx[lc] += tag[p]; tag[lc] += tag[p];，右孩子同理。

pushup：mx[p] = max(mx[lc], mx[rc]);

void apply(int p, ll v){ mx[p]+=v; tag[p]+=v; }
void pushdown(int p){
    if(!tag[p]) return;
    apply(lc, tag[p]); apply(rc, tag[p]);
    tag[p]=0;
}
void rangeAdd(int p,int l,int r,int L,int R,ll v){
    if(L<=l&&r<=R){ apply(p,v); return; }
    pushdown(p);
    if(L<=mid) rangeAdd(lc,l,mid,L,R,v);
    if(R>mid) rangeAdd(rc,mid+1,r,L,R,v);
    pushup(p);
}

易错：pushdown 里忘记给孩子的 tag 累加（只改了孩子的 mx）；或者查询里忘记 pushdown。

B2复合信息

实现「区间加 + 查询区间和与区间平方和」的线段树，说明为什么需要同时维护两个信息。

查看参考答案

为什么需要两个：区间加 v 时，平方和的变化依赖"原来的和"：S2' = S2 + 2v·S1 + k·v²。所以必须同时维护 S1（和）才能正确更新 S2（平方和）。

void apply(int p,int len,ll v){
    s2[p] += 2*v*s1[p] + v*v*len;   // ★ 先用旧 s1 更新 s2
    s1[p] += v*len;
    tag[p] += v;
}

易错（极常见）：先更新 s1[p] 再算 s2[p]，导致用了"新的和"代入公式，结果全错。顺序必须是先 s2 后 s1。

B3综合编程

维护一个序列，支持：① 区间 [l, r] 赋值为 v；② 查询区间 [l, r] 的和。n, m ≤ 105。

查看参考答案

思路：区间赋值需要"赋值标记"。为了区分"没有标记"和"赋值为 0"，标记初值用一个特殊值（如 -1 或 INF）表示"无标记"。

ll sum[MAXN*4], tag[MAXN*4];
// tag[p] = -1 表示无标记；否则表示"整段赋值为 tag[p]"

void build(int p,int l,int r){
    tag[p] = -1;                            // ★ 初始化为"无标记"
    if(l==r){ sum[p]=a[l]; return; }
    build(lc,l,mid); build(rc,mid+1,r);
    pushup(p);
}
void apply(int p,int len,ll v){ sum[p]=v*len; tag[p]=v; }
void pushdown(int p,int l,int r){
    if(tag[p]==-1) return;
    apply(lc, mid-l+1, tag[p]);
    apply(rc, r-mid, tag[p]);
    tag[p] = -1;
}

易错：用 0 表示"无标记"，导致"赋值 0"的操作被忽略；或者 pushdown 后忘记把 tag 恢复为 −1。

延伸：如果同时有"赋值""加""乘"三种操作，需要给标记定义明确的复合优先级（一般是 赋值 > 乘 > 加），这是线段树进阶的经典难点。

B4对比分析

同一个问题「区间加 + 区间和」，分别用树状数组和线段树实现，比较代码长度、常数与适用性。

查看参考答案

代码长度：树状数组（双 BIT）约 25 行；线段树约 70 行。BIT 短很多。

常数：BIT 每次操作约 2×log n 次位运算 + 加法，无递归；线段树每次操作约 4×log n 个节点访问，有递归和 pushdown。BIT 通常快 3~5 倍。

空间：BIT 是 2n，线段树是 4n。

适用性：本题两者都能做；但一旦改成「区间加 + 区间最值」，BIT 立刻失效，线段树只需把 pushup 换成 max 即可。

结论：能用 BIT 就别写线段树；但只要需求超出 BIT 的能力范围（最值、赋值、复合信息），立刻切换到线段树，不要硬凑。

🔴 C组 · 挑战（4题）

C1初赛真题

一棵维护 n = 8 个元素的线段树，查询区间 [2, 7] 最多会访问多少个节点？请列出这些节点。

查看参考答案

区间 [2,7] 的分解：

· 节点1[1,8] 部分相交 → 下访

· 节点2[1,4] 部分相交；节点3[5,8] 部分相交

· 节点4[1,2] 部分相交 → 节点9[2,2] 完全覆盖

· 节点5[3,4] 完全覆盖

· 节点6[5,6] 完全覆盖

· 节点7[7,8] 部分相交 → 节点14[7,7] 完全覆盖

终止节点（直接返回）：9、5、6、14，共 4 个。

被访问的节点总数：1、2、3、4、5、6、7、9、14，共 9 个节点。

规律：每层最多 2 个"完全覆盖"节点，深度 4 层 → 最多 8 个终止节点；加上路径上的节点，总量 O(log n)。

C2势能线段树

给定序列 a（a[i] ≤ 1012），支持：① 区间 [l, r] 每个数开平方（下取整）；② 区间求和。n, m ≤ 105。请设计算法并分析复杂度。

查看参考答案

核心观察（势能）：任何 ≤ 1012 的正整数，最多开 6 次平方就变成 1；1 再开方仍然是 1。所以每个位置的"有效开方次数"≤ 6。

做法：线段树维护 sum 与 mx。开方时：若 mx ≤ 1，整段都是 0/1，开方无影响，直接 return（剪枝）；否则递归到叶子，逐个真正开方。

void rangeSqrt(int p,int l,int r,int L,int R){
    if(mx[p] <= 1) return;              // ★ 剪枝
    if(l==r){ sum[p] = (ll)sqrt((double)sum[p]); mx[p]=sum[p]; return; }
    if(L<=mid) rangeSqrt(lc,l,mid,L,R);
    if(R>mid) rangeSqrt(rc,mid+1,r,L,R);
    pushup(p);
}

复杂度分析：每个位置最多被"真正开方"6 次，所以"递归到叶子"的总次数 ≤ 6n。其余访问都是 O(log n) 的剪枝路径。总复杂度 O((n + m) log n · 6)，可接受。

易错：忘记 mx ≤ 1 的剪枝（退化成 O(nm) 超时）；或者用 sqrt 浮点误差导致大数开方结果偏差（对 ≤ 1012 的数，double 精度足够，但更大时应改用整数二分或 sqrtl）。

C3综合编程

维护序列，支持：① 区间加 v；② 查询区间 [l, r] 的「最大子段和」。n, m ≤ 105。

查看参考答案

思路：节点维护 4 个量：sum、lmax（含左端点的最大子段和）、rmax（含右端点的）、mx。

「区间加 v」如何影响这 4 个量？对长度为 k 的区间：

· sum' = sum + k·v

· lmax' = lmax + v（含左端点的子段必然包含全部或部分前缀；整体加 v 后，最优前缀长度不变，值加 v）

· rmax' = rmax + v，mx' = mx + v（同理）

所以标签可以直接作用：4 个量同时 += v（sum 要 += v*k）。这与"区间加 + 区间最值"的 apply 形式一致。

合并（merge）：见前面拓展案例的公式。

易错：apply 时只给 mx += v 而忘记 lmax/rmax 也加 v；或者 merge 时漏掉跨中点项 L.rmax + R.lmax。

C4思维题

如果要支持「区间加、区间乘、区间赋值、区间求和」四种操作同时存在，该如何定义 lazy 标记的优先级？

查看参考答案

统一形式：把每个节点的变换统一写成 x → a·x + b，再加上一个"是否被赋值覆盖"的标记。赋值操作可以视为特殊的仿射变换（a=0, b=v），但为了效率通常单独维护。

推荐优先级：赋值 > 乘 > 加。含义是：一个标记的"复合顺序"固定为「先赋值，再乘，再加」。

来一个新操作时的更新规则：

· 来"赋值 v"：清空 mul=1、add=0，设 tag=v（因为赋值会覆盖之前一切操作）

· 来"乘 k"：mul *= k、add *= k（tag 不变，它优先级更高）

· 来"加 v"：add += v

下传时：先处理赋值标记（若有），再乘父的 mul，最后加父的 add，即 son = ((son 按赋值调整) × mul) + add。

为什么必须固定顺序？因为 (a+b)×c ≠ a×c+b。如果标记的顺序不统一，同一个 (mul, add) 二元组会表示不同的变换，公式就失效了。这就是"lazy 标记必须能构成一个可复合的运算体系"的含义。

启发：lazy 标记的设计本质是——找到一个变换群（或半群），使得"标记作用于信息"和"标记之间复合"都有封闭、可计算的表达式。这是线段树能处理各种复杂操作的理论基础。

🏆 洛谷原题精选（12道）

以下题目均与线段树相关，按难度从入门到提高排列。

1
P3372
【模板】线段树 1入门
2
P1531
I Hate It普及-
3
P1816
忠诚普及-
4
P1198
最大数普及+
5
P3870
开关提高
6
P2574
XOR的艺术提高
7
P3373
【模板】线段树 2提高
8
P2023
维护序列（乘加双标记）提高
9
P4588
数学计算提高
10
P4145
花神游历各国（区间开方）提高
11
P1471
方差提高
12
P2894
Hotel G提高