核心逻辑与数学原理
当线段树需要同时维护多种区间修改操作（如区间同时存在乘法修改、加法修改）或维护非线性信息（如区间平方和）时，核心难点在于多标记的代数优先级定义与非线性状态的代数展开。
1. 区间乘法加法混合的代数维护
假设当前节点维护的区间和为 $S$，该节点先后被施加了乘以一个数 $m$ 和加上一个数 $a$ 的操作。为了用统一的代数式表示任何时刻的状态，我们将复合变换定义为：
$$S_{new} = S \times m + a \times len$$
其中 $len$ 为当前区间长度。
若此时区间再次读入一个乘法操作（乘以 $M$）和加法操作（加上 $A$），根据结合律与分配律，新的状态为：
$$S_{final} = (S \times m + a \times len) \times M + A \times len = S \times (m \times M) + (a \times M + A) \times len$$
由此推导得出了多标记合并的硬核法则：
- 新乘法标记：$m' = m \times M$
- 新加法标记：$a' = a \times M + A$
结论：乘法标记会直接改变原有的加法标记，而加法标记对原有的乘法标记无影响。因此，乘法标记的优先级高于加法标记。在下传标记时，必须先处理乘法，再处理加法。
2. 区间平方和的代数展开
线段树维护区间平方和 $\\sum X_i^2$ 时，若执行区间加 $v$ 操作，每个元素 $X_i \leftarrow X_i + v$。利用完全平方公式展开：
$$\sum (X_i + v)^2 = \sum (X_i^2 + 2vX_i + v^2) = \sum X_i^2 + 2v \sum X_i + v^2 \sum 1$$
状态转移方程变为：
$$S_{sq ext{new}} = S_{sq} + 2v \times S_{sum} + v^2 \times len$$
这意味着，要维护区间平方和，必须同时维护区间一阶和（$S_{sum}$）。
状态设计与算法推导
1. 乘法加法混合线段树状态
每个节点维护三个值：sum（区间和）、mul（乘法懒标记，初始化为 $1$）、add（加法懒标记，初始化为 $0$）。
标记下传（Pushdown）推导
对于节点 $u$ 的左子节点 $ls$（$ls = u \ll 1$）：
- 更新子节点的数据值（必须严格按照先乘后加的顺序）：
$$sum[ls] = (sum[ls] \times mul[u] + add[u] \times len_{ls}) \pmod P$$
- 更新子节点的标记值：
$$mul[ls] = (mul[ls] \times mul[u]) \pmod P$$
$$add[ls] = (add[ls] \times mul[u] + add[u]) \pmod P$$
- 右子节点同理。下传后，恢复物理基准状态：
mul[u] = 1, add[u] = 0。
2. 区间平方和线段树状态
每个节点维护：sum1（一阶和 $\\sum X_i$）、sum2（二阶平方和 $\\sum X_i^2$）、lazy（加法标记）。
标记下传（Pushdown）推导
对于子节点 $ls$，若父节点有加法标记 $v$：
- 先根据一阶和更新二阶和：$sum2[ls] = sum2[ls] + 2 \times v \times sum1[ls] + v \times v \times len_{ls}$
- 再更新一阶和：$sum1[ls] = sum1[ls] + v \times len_{ls}$
- 累加懒标记：$lazy[ls] = lazy[ls] + v$
C++ 标准源码（NOIP风格：以区间乘法+加法为例）
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
inline long long read() {
long long x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
const int MAXN = 100005;
long long sum[MAXN << 2];
long long mul[MAXN << 2];
long long add[MAXN << 2];
long long a[MAXN];
long long MOD; // NOIP 混合常考大质数取模
inline void pushup(int u) {
sum[u] = (sum[u << 1] + sum[u << 1 | 1]) % MOD;
}
// 核心混合下传
inline void pushdown(int u, int l, int r) {
int m = (l + r) >> 1;
int ls = u << 1, rs = u << 1 | 1;
// 1. 处理左子树
sum[ls] = (sum[ls] * mul[u] % MOD + add[u] * (m - l + 1) % MOD) % MOD;
mul[ls] = (mul[ls] * mul[u]) % MOD;
add[ls] = (add[ls] * mul[u] % MOD + add[u]) % MOD; // 致命踩坑点：子节点的原加法标记必须先乘上父节点的乘法标记
// 2. 处理右子树
sum[rs] = (sum[rs] * mul[u] % MOD + add[u] * (r - m) % MOD) % MOD;
mul[rs] = (mul[rs] * mul[u]) % MOD;
add[rs] = (add[rs] * mul[u] % MOD + add[u]) % MOD;
// 3. 重置当前节点标记
mul[u] = 1;
add[u] = 0;
}
void build(int u, int l, int r) {
mul[u] = 1; // 致命踩坑点：乘法标记初始化必须为 1，误初始为 0 会导致整棵树数据直接被抹除
add[u] = 0;
if (l == r) {
sum[u] = a[l] % MOD;
return;
}
int m = (l + r) >> 1;
build(u << 1, l, m);
build(u << 1 | 1, m + 1, r);
pushup(u);
}
void update_mul(int u, int l, int r, int ql, int qr, long long v) {
if (ql <= l && r <= qr) {
sum[u] = (sum[u] * v) % MOD;
mul[u] = (mul[u] * v) % MOD;
add[u] = (add[u] * v) % MOD; // 乘法操作直接对当前节点的加法标记生效
return;
}
pushdown(u, l, r);
int m = (l + r) >> 1;
if (ql <= m) update_mul(u << 1, l, m, ql, qr, v);
if (qr > m) update_mul(u << 1 | 1, m + 1, r, ql, qr, v);
pushup(u);
}
void update_add(int u, int l, int r, int ql, int qr, long long v) {
if (ql <= l && r <= qr) {
sum[u] = (sum[u] + v * (r - l + 1) % MOD) % MOD;
add[u] = (add[u] + v) % MOD; // 加法操作不影响当前节点的乘法标记
return;
}
pushdown(u, l, r);
int m = (l + r) >> 1;
if (ql <= m) update_add(u << 1, l, m, ql, qr, v);
if (qr > m) update_add(u << 1 | 1, m + 1, r, ql, qr, v);
pushup(u);
}
long long query(int u, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return sum[u];
pushdown(u, l, r);
int m = (l + r) >> 1;
long long res = 0;
if (ql <= m) res = (res + query(u << 1, l, m, ql, qr)) % MOD;
if (qr > m) res = (res + query(u << 1 | 1, m + 1, r, ql, qr)) % MOD;
return res;
}
int main() {
int n = read(), m = read();
MOD = read();
for (int i = 1; i <= n; ++i) a[i] = read();
build(1, 1, n);
while (m--) {
int opt = read();
if (opt == 1) {
int ql = read(), qr = read();
long long v = read();
update_mul(1, 1, n, ql, qr, v);
} else if (opt == 2) {
int ql = read(), qr = read();
long long v = read();
update_add(1, 1, n, ql, qr, v);
} else {
int ql = read(), qr = read();
printf("%lld\n", query(1, 1, n, ql, qr));
}
}
return 0;
}
NOIP 实战避坑指南
1. 乘法标记错误的初始化
在多标记线段树中，选手常习惯性地在 build 或声明时将所有数组清零。如果将乘法标记 mul[] 误初始化为 0，执行 pushdown 时，sum[ls] * mul[u] 将使得所有子树节点的数据直接变成 0。必须在建树时，显式将所有节点的 mul[u] 赋值为 1。
2. 标记下传时的取模非原子性
在执行 add[ls] = (add[ls] * mul[u] + add[u]) % MOD; 时，乘法和加法交织在一起。极易出现的低级错误是漏掉中间步骤的取模，导致 add[ls] * mul[u] 直接溢出 long long（最大可达 $(10^9) \times (10^9) = 10^{18}$，若连续两个未取模的大数相乘会直接截断）。每一阶段的乘法和加法结果都必须立刻包裹 `% MOD`。
3. 平方和维护中的更新顺序颠倒
在线段树维护区间平方和的 pushdown 中，必须先更新平方和 sum2，再更新一阶和 `sum1。因为sum2的更新公式里包含sum1（即 $2v \times sum1$）。如果先将sum1加上了 $v \times len$，此时的sum1已经是未来的状态，再代入sum2` 的计算公式就会引发重复计算，导致数学逻辑彻底崩塌。
经典 NOIP/洛谷 真题
1. 洛谷 P3373 【模板】线段树 2
- 题意描述：已知一个数列，你需要进行下面三种操作：将某区间每个数乘上 $x$；将某区间每个数加上 $x$；求某区间每个数的和模 $P$ 的值。
- 问题本质：双标记线段树标准工业级基准。
- 核心解题思路：如上文所述，核心在于
pushdown时严格遵循 $S \times mul + add$ 的状态定义。当遇到区间乘法修改 $v$ 时，将当前节点的sum,mul,add全部乘以 $v$；遇到区间加法修改 $v$ 时，仅将sum加上 $v \times len$，add加上 $v$。通过算子优先级的硬性规定解决标记冲突。
2. 洛谷 P1471 矩形方差 / 洛谷 P6327 区间正弦和（变种拓展）
- 题意描述：维护一个序列，支持区间加实数 $x$，并实时查询区间的方差。
- 问题本质：非线性高阶信息的区间维护。
- 核心解题思路：方差公式为 $D = \frac{1}{n}\sum X_i^2 - \bar{X}^2$。因此，问题本质上等价于要求线段树同时高效维护区间的“一阶和 $\\sum X_i$”与“平方和 $\\sum X_i^2$”。使用完全平方公式展开，通过一阶和的变化量实时推进二阶平方和的增量，单次修改复杂度 $O(\log N)$。