目录前言一、多个区间操作的核心痛点优先级决定结果二、经典组合 1区间乘 区间加洛谷 P3373【模板】线段树 22.1 核心推导先乘后加的公式简化推导过程关键结论2.2 结构体与核心函数设计2.2.1 结构体定义2.2.2 核心辅助函数1pushup整合左右孩子信息2lazy更新当前节点的标记与区间和3pushdown下放标记给左右孩子2.2.3 建树、修改、查询操作1build建树2modify区间修改支持乘 / 加3query区间查询和2.3 完整实战代码洛谷 P3373 AC 代码2.4 代码测试与验证题目输入示例手动计算过程三、经典组合 2区间重置 区间加洛谷 P1253 扶苏的问题3.1 核心逻辑重置标记的 “覆盖性”3.2 结构体与核心函数设计3.2.1 结构体定义3.2.2 核心辅助函数1pushup整合左右孩子最大值2lazy更新当前节点的标记与最大值3pushdown下放标记给左右孩子3.2.3 建树、修改、查询操作1build建树2modify区间修改支持重置 / 加3query区间查询最大值3.3 完整实战代码洛谷 P1253 AC 代码3.4 代码测试与验证题目输入示例手动计算过程四、多区间操作的通用解题框架4.1 步骤 1确定操作优先级4.2 步骤 2设计结构体与懒标记4.3 步骤 3实现核心辅助函数4.4 步骤 4实现建树、修改、查询五、高频易错点总结5.1 优先级顺序错误5.2 懒标记未清空5.3 重置标记未清空加法标记5.4 数据类型溢出5.5 线段树空间开太小总结前言在掌握了基础线段树、区间修改单懒标记后算法竞赛中常会遇到更复杂的场景 ——多个区间修改操作共存比如 “区间加 区间乘”“区间重置 区间加”。此时单懒标记已无法满足需求核心难点在于确定操作的执行优先级不同修改操作的顺序会直接影响最终结果若处理不当不仅会导致答案错误还可能引发精度问题。本文将深入拆解多个区间操作的核心逻辑聚焦懒标记的优先级设计通过洛谷经典模板题区间加 区间乘、区间重置 区间加手把手实现带多懒标记的线段树让你彻底攻克这一进阶难点下面就让我们正式开始吧一、多个区间操作的核心痛点优先级决定结果先看一个直观的例子假设对数字x先执行 “加 3” 再执行 “乘 2”结果是(x3)*2 2x6若先执行 “乘 2” 再执行 “加 3”结果是2x3。两种顺序的结果天差地别这就是多个区间操作的核心痛点 ——操作顺序直接影响最终结果。线段树的多个区间操作本质是懒标记的叠加与下放。当一个节点同时存在多个懒标记时必须明确 “先执行哪个操作、后执行哪个操作”即确定懒标记的优先级。优先级的设计需满足两个原则结果正确性确保标记下放后子节点的信息与实际操作顺序一致计算简便性避免复杂的公式推导减少代码出错概率。常见的多个区间操作组合及优先级结论操作组合优先级结论核心原因区间乘mul 区间加add先乘后加先乘后加的公式可简化无精度损失先加后乘会出现除法导致精度问题区间重置set 区间加add先重置后加重置操作会覆盖之前的所有状态加操作仅作用于重置后的数值接下来我们通过两个经典例题详细讲解不同组合的实现逻辑。二、经典组合 1区间乘 区间加洛谷 P3373【模板】线段树 2题目链接https://www.luogu.com.cn/problem/P3373这是最常见的多区间操作组合要求支持 “区间乘 k”“区间加 k”“区间求和取模” 三种操作。我们先推导优先级公式再实现完整代码。2.1 核心推导先乘后加的公式简化假设节点当前的懒标记为mul0乘法标记和add0加法标记表示该节点的所有元素需执行x x * mul0 add0。现在新增一组操作“乘 m” 和 “加 a”需要推导新的懒标记mul1和add1。推导过程原操作x → x * mul0 add0新增操作先乘 m →(x * mul0 add0) * m再加 a →(x * mul0 add0) * m a展开后x * (mul0 * m) (add0 * m a)因此新的懒标记满足新乘法标记mul1 mul0 * m取模新加法标记add1 add0 * m a取模。关键结论乘法标记的初始值为1因为x * 1 x不影响原始值加法标记的初始值为0因为x 0 x不影响原始值标记下放时必须先传递乘法标记再传递加法标记确保子节点的操作顺序正确。2.2 结构体与核心函数设计2.2.1 结构体定义需要维护的信息区间左右边界l/r区间和sum需取模乘法懒标记mul初始 1加法懒标记add初始 0。C 代码typedef long long LL; const int N 1e5 10; int mod; // 模数由输入指定 struct node { int l, r; LL sum, mul, add; // sum:区间和mul:乘法标记add:加法标记 } tr[N 2]; // 线段树空间开4倍2.2.2 核心辅助函数多区间操作的核心是lazy函数更新当前节点标记和pushdown函数下放标记需严格遵循 “先乘后加” 的优先级。1pushup整合左右孩子信息基础函数区间和 左孩子和 右孩子和取模void pushup(int p) { tr[p].sum (tr[p 1].sum tr[p 1 | 1].sum) % mod; }2lazy更新当前节点的标记与区间和接收新增的乘法因子m和加法因子a根据 “先乘后加” 更新节点信息void lazy(int p, LL m, LL a) { auto t tr[p]; // 1. 更新区间和sum (sum * m a * 区间长度) % mod t.sum (t.sum * m a * (t.r - t.l 1)) % mod; // 2. 更新乘法标记mul (mul * m) % mod t.mul t.mul * m % mod; // 3. 更新加法标记add (add * m a) % mod t.add (t.add * m a) % mod; }3pushdown下放标记给左右孩子必须先下放乘法标记再下放加法标记确保子节点的操作顺序正确void pushdown(int p) { auto t tr[p]; // 只有非初始标记时才需要下放mul≠1 或 add≠0 if (t.mul ! 1 || t.add ! 0) { // 下放标记给左孩子传递当前节点的 mul 和 add lazy(p 1, t.mul, t.add); // 下放标记给右孩子传递当前节点的 mul 和 add lazy(p 1 | 1, t.mul, t.add); // 清空当前节点标记恢复初始状态 t.mul 1; t.add 0; } }2.2.3 建树、修改、查询操作1build建树初始化节点的区间、和、标记mul1add0void build(int p, int l, int r, LL a[]) { tr[p] {l, r, a[l] % mod, 1, 0}; // 初始mul1add0 if (l r) return; int mid (l r) 1; build(p 1, l, mid, a); build(p 1 | 1, mid 1, r, a); pushup(p); }2modify区间修改支持乘 / 加根据操作类型调用lazy函数更新标记核心逻辑与单标记一致// 区间修改[x,y] 执行 乘m 加am1时仅加a0时仅乘 void modify(int p, int x, int y, LL m, LL a) { auto t tr[p]; if (x t.l t.r y) { lazy(p, m, a); // 完全覆盖直接更新标记 return; } pushdown(p); // 未完全覆盖先下放标记 int mid (t.l t.r) 1; if (x mid) modify(p 1, x, y, m, a); if (y mid) modify(p 1 | 1, x, y, m, a); pushup(p); // 整合左右孩子信息 }3query区间查询和查询逻辑与单标记一致需在递归前下放标记LL query(int p, int x, int y) { auto t tr[p]; if (x t.l t.r y) { return t.sum % mod; } pushdown(p); // 下放标记确保子节点信息最新 int mid (t.l t.r) 1; LL res 0; if (x mid) res (res query(p 1, x, y)) % mod; if (y mid) res (res query(p 1 | 1, x, y)) % mod; return res; }2.3 完整实战代码洛谷 P3373 AC 代码结合题目要求处理输入输出支持三种操作1 x y k区间 [x,y] 乘 k2 x y k区间 [x,y] 加 k3 x y查询区间 [x,y] 和对 mod 取模。完整代码#include iostream using namespace std; typedef long long LL; const int N 1e5 10; int mod; struct node { int l, r; LL sum, mul, add; } tr[N 2]; void pushup(int p) { tr[p].sum (tr[p 1].sum tr[p 1 | 1].sum) % mod; } void lazy(int p, LL m, LL a) { auto t tr[p]; t.sum (t.sum * m a * (t.r - t.l 1)) % mod; t.mul t.mul * m % mod; t.add (t.add * m a) % mod; } void pushdown(int p) { auto t tr[p]; if (t.mul ! 1 || t.add ! 0) { lazy(p 1, t.mul, t.add); lazy(p 1 | 1, t.mul, t.add); t.mul 1; t.add 0; } } void build(int p, int l, int r, LL a[]) { tr[p] {l, r, a[l] % mod, 1, 0}; if (l r) return; int mid (l r) 1; build(p 1, l, mid, a); build(p 1 | 1, mid 1, r, a); pushup(p); } void modify(int p, int x, int y, LL m, LL a) { auto t tr[p]; if (x t.l t.r y) { lazy(p, m, a); return; } pushdown(p); int mid (t.l t.r) 1; if (x mid) modify(p 1, x, y, m, a); if (y mid) modify(p 1 | 1, x, y, m, a); pushup(p); } LL query(int p, int x, int y) { auto t tr[p]; if (x t.l t.r y) { return t.sum % mod; } pushdown(p); int mid (t.l t.r) 1; LL res 0; if (x mid) res (res query(p 1, x, y)) % mod; if (y mid) res (res query(p 1 | 1, x, y)) % mod; return res; } int main() { ios::sync_with_stdio(false); cin.tie(0); int n, q; cin n q mod; LL a[N]; for (int i 1; i n; i) { cin a[i]; a[i] % mod; // 初始值取模 } build(1, 1, n, a); while (q--) { int op, x, y; cin op x y; if (op 1) { // 操作1区间[x,y]乘k LL k; cin k; modify(1, x, y, k, 0); // a0仅乘 } else if (op 2) { // 操作2区间[x,y]加k LL k; cin k; modify(1, x, y, 1, k); // m1仅加 } else { // 操作3查询区间[x,y]和 cout query(1, x, y) endl; } } return 0; }2.4 代码测试与验证题目输入示例5 5 38 1 5 4 2 3 2 1 4 1 // 区间[1,4]加1 3 2 5 // 查询[2,5]和 1 2 4 2 // 区间[2,4]乘2 2 3 5 5 // 区间[3,5]加5 3 1 4 // 查询[1,4]和手动计算过程初始数组[1,5,4,2,3]mod38操作 2加 1后[2,6,5,3,3][2,5] 和 653317操作 1乘 2后[2,12,10,6,3]操作 2加 5后[2,12,15,11,8][1,4] 和 212151140 mod382输出结果17、2与题目示例一致。三、经典组合 2区间重置 区间加洛谷 P1253 扶苏的问题题目链接https://www.luogu.com.cn/problem/P1253另一类高频组合是“区间重置将区间所有元素改为 x 区间加将区间所有元素加 x”。核心优先级是先重置后加—— 重置操作会覆盖之前的所有状态加操作仅作用于重置后的数值。3.1 核心逻辑重置标记的 “覆盖性”假设节点存在“重置标记”和“加法标记”若先执行重置改为 x再执行加 a则最终值为x a若先执行加 a再执行重置改为 x则最终值为x加法标记失效。因此重置标记的优先级高于加法标记标记下放时需先传递重置标记再传递加法标记。同时重置标记会清空之前的加法标记因为重置后加法操作需重新计算。3.2 结构体与核心函数设计3.2.1 结构体定义需要维护的信息区间左右边界l/r区间最大值max题目要求查询最大值加法懒标记add初始 0重置懒标记update初始 0标记状态st是否有重置标记初始 false。C 代码typedef long long LL; const int N 1e6 10; // 数据量较大开1e610 struct node { int l, r; LL max, add, update; bool st; // sttrue表示有重置标记 } tr[N 2];3.2.2 核心辅助函数1pushup整合左右孩子最大值void pushup(int p) { tr[p].max max(tr[p 1].max, tr[p 1 | 1].max); }2lazy更新当前节点的标记与最大值根据操作类型重置 / 加更新节点信息遵循 “先重置后加”// st是否重置update重置值add增加值 void lazy(int p, bool st, LL update_val, LL add_val) { auto t tr[p]; // 1. 先处理重置优先级更高 if (st) { t.max update_val; // 重置为指定值 t.add 0; // 重置后清空加法标记 t.update update_val; t.st true; } // 2. 再处理加法 t.max add_val; t.add add_val; }3pushdown下放标记给左右孩子先下放重置标记再下放加法标记确保子节点操作顺序正确void pushdown(int p) { auto t tr[p]; // 有重置标记或加法标记时下放 if (t.st || t.add ! 0) { // 下放给左孩子 lazy(p 1, t.st, t.update, t.add); // 下放给右孩子 lazy(p 1 | 1, t.st, t.update, t.add); // 清空当前节点标记 t.st false; t.update 0; t.add 0; } }3.2.3 建树、修改、查询操作1build建树void build(int p, int l, int r, LL a[]) { tr[p] {l, r, a[l], 0, 0, false}; if (l r) return; int mid (l r) 1; build(p 1, l, mid, a); build(p 1 | 1, mid 1, r, a); pushup(p); }2modify区间修改支持重置 / 加// sttrue重置false加法val重置值/增加值 void modify(int p, int x, int y, bool st, LL val) { auto t tr[p]; if (x t.l t.r y) { if (st) { // 重置操作add_val0 lazy(p, true, val, 0); } else { // 加法操作stfalseupdate_val0 lazy(p, false, 0, val); } return; } pushdown(p); int mid (t.l t.r) 1; if (x mid) modify(p 1, x, y, st, val); if (y mid) modify(p 1 | 1, x, y, st, val); pushup(p); }3query区间查询最大值LL query(int p, int x, int y) { auto t tr[p]; if (x t.l t.r y) { return t.max; } pushdown(p); int mid (t.l t.r) 1; LL res -1e18; // 初始值设为极小值 if (x mid) res max(res, query(p 1, x, y)); if (y mid) res max(res, query(p 1 | 1, x, y)); return res; }3.3 完整实战代码洛谷 P1253 AC 代码题目要求支持三种操作1 l r x区间 [l,r] 重置为 x2 l r x区间 [l,r] 加 x3 l r查询区间 [l,r] 最大值。完整代码#include iostream #include cstdio using namespace std; typedef long long LL; const int N 1e6 10; struct node { int l, r; LL max, add, update; bool st; } tr[N 2]; void pushup(int p) { tr[p].max max(tr[p 1].max, tr[p 1 | 1].max); } void lazy(int p, bool st, LL update_val, LL add_val) { auto t tr[p]; if (st) { t.max update_val; t.add 0; t.update update_val; t.st true; } t.max add_val; t.add add_val; } void pushdown(int p) { auto t tr[p]; if (t.st || t.add ! 0) { lazy(p 1, t.st, t.update, t.add); lazy(p 1 | 1, t.st, t.update, t.add); t.st false; t.update 0; t.add 0; } } void build(int p, int l, int r, LL a[]) { tr[p] {l, r, a[l], 0, 0, false}; if (l r) return; int mid (l r) 1; build(p 1, l, mid, a); build(p 1 | 1, mid 1, r, a); pushup(p); } void modify(int p, int x, int y, bool st, LL val) { auto t tr[p]; if (x t.l t.r y) { if (st) { lazy(p, true, val, 0); } else { lazy(p, false, 0, val); } return; } pushdown(p); int mid (t.l t.r) 1; if (x mid) modify(p 1, x, y, st, val); if (y mid) modify(p 1 | 1, x, y, st, val); pushup(p); } LL query(int p, int x, int y) { auto t tr[p]; if (x t.l t.r y) { return t.max; } pushdown(p); int mid (t.l t.r) 1; LL res -1e18; if (x mid) res max(res, query(p 1, x, y)); if (y mid) res max(res, query(p 1 | 1, x, y)); return res; } int main() { int n, q; scanf(%d%d, n, q); // 用scanf加速输入 LL a[N]; for (int i 1; i n; i) { scanf(%lld, a[i]); } build(1, 1, n, a); while (q--) { int op, l, r; scanf(%d%d%d, op, l, r); if (op 1) { // 操作1重置为x LL x; scanf(%lld, x); modify(1, l, r, true, x); } else if (op 2) { // 操作2加x LL x; scanf(%lld, x); modify(1, l, r, false, x); } else { // 操作3查询最大值 printf(%lld\n, query(1, l, r)); } } return 0; }3.4 代码测试与验证题目输入示例6 6 1 1 4 5 1 4 1 1 2 6 // 区间[1,2]重置为6 2 3 4 2 // 区间[3,4]加2 3 1 4 // 查询[1,4]最大值 3 2 3 // 查询[2,3]最大值 1 1 6 -1 // 区间[1,6]重置为-1 3 1 6 // 查询[1,6]最大值手动计算过程初始数组[1,1,4,5,1,4]操作 1重置后[6,6,4,5,1,4]操作 2加 2后[6,6,6,7,1,4]查询 [1,4] 最大值7查询 [2,3] 最大值6操作 1重置后[-1,-1,-1,-1,-1,-1]查询 [1,6] 最大值-1输出结果7、6、-1与题目示例一致。四、多区间操作的通用解题框架通过以上两个例子我们可以总结出多区间操作的通用解题框架无论遇到哪种组合都可以按以下步骤思考4.1 步骤 1确定操作优先级这是最核心的一步需明确不同操作的执行顺序。常见优先级规则覆盖类操作如重置 算术类操作如乘、加算术类操作乘 加避免精度损失。4.2 步骤 2设计结构体与懒标记结构体需包含区间边界、维护的核心信息和 / 最大值 / 最小值、每个操作对应的懒标记懒标记初始值不影响原始数据如乘标记 1加标记 0重置标记 false。4.3 步骤 3实现核心辅助函数pushup根据左右孩子的信息整合父节点信息固定逻辑与单标记一致lazy根据优先级更新当前节点的核心信息和懒标记关键按优先级顺序更新pushdown按优先级顺序将当前节点的懒标记下放给左右孩子然后清空当前节点标记关键顺序与 lazy 函数一致。4.4 步骤 4实现建树、修改、查询建树初始化节点信息和懒标记修改完全覆盖则调用 lazy 函数否则 pushdown 后递归孩子最后 pushup查询完全覆盖则返回核心信息否则 pushdown 后递归孩子整合结果。五、高频易错点总结多区间操作的代码复杂度较高新手容易踩坑以下是五大高频易错点5.1 优先级顺序错误这是最致命的错误比如 “先加后乘”“先加后重置”会导致结果错误或精度损失。解决方法先推导公式再编写代码确保 lazy 和 pushdown 的操作顺序一致。5.2 懒标记未清空pushdown 后未将当前节点的标记恢复为初始状态导致标记被重复下放多次执行同一操作。5.3 重置标记未清空加法标记重置操作会覆盖之前的所有状态若未清空加法标记后续加法会作用于重置前的数值导致结果错误。5.4 数据类型溢出区间和、最大值等可能超过 int 范围必须用 long long 存储避免溢出。5.5 线段树空间开太小多区间操作的线段树空间仍需开 4 倍原始数组大小否则会出现数组越界尤其是数据量达 1e6 时。总结多个区间操作的核心是懒标记的优先级设计只要明确操作顺序、推导正确的叠加公式再遵循通用解题框架就能轻松实现。本文通过两个经典例题详细讲解了 “区间乘 区间加”“区间重置 区间加” 的实现逻辑涵盖了公式推导、结构体设计、核心函数编写、完整代码实现等环节帮助大家彻底攻克这一进阶难点。线段树的灵活性在于其可维护的信息种类繁多而多区间操作是线段树进阶的必经之路。掌握了多懒标记的处理方法你就能应对算法竞赛中绝大多数区间操作问题。建议大家多刷题、多推导加深对优先级的理解真正做到举一反三创作不易如果本文对你有帮助欢迎点赞、收藏、关注三连