线段树模板P3373：懒标记先乘后加的顺序与实现详解

线段树模板题里P3373 大概是很多人第一道“背模板也背不明白”的题。倒不是说代码长而是它同时要求区间加和区间乘两个懒标记一叠加很多原本会写线段树 1 的人瞬间不知道下传顺序怎么处理。我第一次交的时候直接在 pushdown 里按直觉先加了再乘结果样例过了随手构造一组数据就错得离谱。后来把懒标记合并当成一个数学表达式来推再回头看这道题发现它考的就是一件小事加法标记在乘法面前必须跟着被放大。这篇博客就把我绕过的弯、整理过的模板、以及调这种题时用的验证方法完整写一遍希望能让同样被 P3373 卡过的人一次想明白。1. 这道“模板题”的真正难点不是代码长而是懒标记的顺序1.1 题目模型区间加、区间乘、区间求和、统一取模P3373 的要求很直接维护一个长度为 n 的数组支持三种操作把某个区间内每个数都乘上一个数把某个区间内每个数都加上一个数查询某个区间内所有数的和。所有结果对一个给定的模数 p 取模。注意乘法和加法是交替出现的没有任何限制说“先所有乘完再所有加”。这里有几个约束很容易被忽略。第一n 和操作数都是 1e5 级别所以必须用 O(log n) 的数据结构暴力更新不可行。第二模数 p 不一定是质数而且可能很大这意味着你不能靠“乘法的模逆元”之类的技巧来偷懒老老实实维护懒标记。第三操作中给的乘数、加数可能超过 int 范围通常要开 long long 才安全。很多人只盯着线段树本身结果在类型转换上栽跟头这类问题我在后面会专门说。1.2 为什么线段树1的板子在这里直接失效如果只做区间加线段树只需要一个加法懒标记。当一个节点被完整覆盖时把加法标记加进 add把区间和加上“长度 × 加数”当需要访问它的子节点时再把 add 往下传。整个过程是线性的非常简单。一旦加入乘法情况就变了。同一个节点上可能先积累了一个加法标记然后又来了一个乘法标记也可能先乘后加、再加再乘、再乘再加……这个节点到底应该怎么表示如果把 add 和 mul 分开存那么两个标记谁先谁后必须有一个明确的规则否则同一个实际区间在不同时刻会得到不同的结果。线段树 1 的板子完全没有“乘法”这个概念所以直接套上去一定错而且错得非常隐蔽——小数据可能顺手就过换一组数据就 WA。1.3 懒标记到底是什么延迟更新的“欠账”我想用一个比喻来解释懒标记它相当于一个节点对子节点欠了一笔账。区间更新时如果一个节点对应的区间完全落在操作范围内我不着急把变化下沉到叶子而是先把变化记在这个节点的账本上同时把该节点的区间和立刻修正正确。以后如果查询或更新涉及它的子区间再把账本里的欠账结算给子节点。这样每个操作最多只走 O(log n) 个节点复杂度才有保证。线段树 2 里每个节点的账本有两项乘了多少、加了多少。难点在于“欠账”不是简单相加而是会互相影响——新欠一笔乘法账时之前欠的加法账也要跟着放大新欠一笔加法账时之前欠的乘法账保持不动。能不能正确处理这种“账中带账”就是这道题的核心分水岭。后面我会用公式严格推导这个顺序。2. 先乘后加推导懒标记合并公式的完整过程2.1 用“实际值 原值 × 乘法标记 加法标记 × 长度”统一表示假设某个节点代表的区间长度为 len这个区间里每个元素真正的值在应用该节点自身的懒标记之前可以认为是一个“原始值”。这个原始值可能是更下层子节点已经结算完毕的值也可能是之前操作残留在子节点里的值。我们约定当前节点的懒标记表示还需要对它的整个区间统一施加一轮“先乘后加”的变换实际值 原始值 × mul[node] add[node] × len注意 add[node] 要乘以长度。为什么因为区间和是每个元素的和。如果每个元素都加 k整个区间的和就增加 k × len。而 mul[node] 不需要乘长度因为每个元素乘 k区间和自然也乘 k。这个统一表达式是整个模板的地基。后续所有标记合并都从它出发。我把 len 写进表达式而不是单独记一个“区间和变化量”是为了避免在 apply_add 时忘记乘长度。很多新手写线段树 2 的 bug 其实就漏在这个长度上。2.2 给区间乘一个数时乘法标记和加法标记分别怎么变现在考虑对一个已经带有懒标记的节点整体乘一个数 k。也就是说该节点的“已承诺”变换是值 原值 × mul add × len。现在又要在此基础上整体乘以 k那么新期望是新值 (原值 × mul add × len) × k 原值 × (mul × k) (add × k) × len所以乘法标记应该变成 mul × k加法标记应该变成 add × k区间和 tree 也要变成 tree × k。这里最容易出错的是最后一条add 也要乘 k。因为原本欠着“每个元素加 add”这笔账现在所有元素整体又乘了 k那这笔加法账自然要乘以 k 才行。我见过不少模板在 apply_mul 里只更新 tree 和 mul不更新 add结果就是在“乘完再查子区间”的时候答案对不上。顺带说如果这个节点没有任何历史加法账add0那 add × k 仍然是 0看起来“不处理也行”。但只要之前有过区间加操作add 非 0这里就躲不过去。P3373 这种混合操作题里这种情况几乎必然出现。2.3 给区间加一个数时只有加法标记变再来看整体加一个数的情况。基于同样的表达式新值 原值 × mul add × len k × len 原值 × mul (add k) × len因此加法标记 add 变成 add k区间和 tree 增加 k × len乘法标记 mul 完全不变。理由也很直观整体加 k 不会改变之前已经乘过的倍数所以乘法账不动加法账上再叠一笔新账。这两个推导合起来就是线段树 2 的核心乘法操作会同时放大乘法和加法两类标记加法操作只会增加加法标记。只要记住这个不对称性代码就不容易写错。2.4 pushdown 为什么必须先传乘法再传加法当一个非完整覆盖的更新或查询需要访问子节点时必须先把当前节点欠的账发给两个子节点。这里的顺序为什么必须是“先传乘法、再传加法”因为我们在 2.1 里约定的变换本身是“先乘后加”实际值 原值 × mul add × len。父节点的懒标记用这个顺序定义下发给子节点时自然也要按这个顺序合并到子节点的账本里。具体地设子节点原来的标记是 mul_child、add_child它代表的实际值是 原值 × mul_child add_child × len_child。现在父节点的乘法标记 m、加法标记 a 要作用到这个子区间那么新的期望是(原值 × mul_child add_child × len_child) × m a × len_child 原值 × (mul_child × m) (add_child × m a) × len_child所以你如果按顺序调用 apply_mul(child, m)再调用 apply_add(child, a)代码正好实现这个公式先传乘法让子节点的 mul 和 add 都乘 m再传加法让子节点的 add 加 a。反过来先加后乘就变成了 (add_child a) × m和正确结果 add_child × m a 不等价。只在 a0 时碰巧相等所以样例能过、数据一大就挂。提示不要把“先乘后加”理解成“先执行乘法操作再执行加法操作”。这里指的是懒标记合并公式中的变换顺序。操作历史可能是先加后乘但合并后统一用“先乘后加”的表达式表示之所以可以这样统一是因为乘法分配律。推导时抓住实际值 原值 × 乘法标记 加法标记 × 长度 这个公式就不会乱。3. 完整模板逐段拆解build、pushdown、更新与查询3.1 数组开多大、为什么乘法标记初始为 1线段树一般用完全二叉树下标法组织节点根是 1左儿子 2×node右儿子 2×node1。数组要多开四倍也就是 N2而不是 N×2。因为满二叉树下标范围可能超过 2N开到 4N 基本够用。这里 N 是数据的最大长度不是操作数。很多人把 N 定义成 1e5 后直接开tree[200005]遇到 n 接近 1e5 时会越界。乘法懒标记的单位元是 1因为任何数乘 1 等于它自己加法懒标记的单位元是 0。所以初始化节点时mul 要赋成 1add 要赋成 0。如果忘记初始化 mul全局变量默认是 0那么 pushdown 里判断mul[node] ! 1就会永远成立每次查询都把子节点清掉完全乱套。3.2 build 与初始化build 的过程就是递归建树。对叶子节点存下a[l] % p对内部节点存下左右儿子之和再取模。因为叶子节点可能有取模后的值内部节点求和也要及时取模否则后面乘法一放大就超出预期。在 build 的入口处直接设置mul[node] 1; add[node] 0;这样能保证所有被访问到的节点都有正确的初始标记。如果为了省事也可以靠全局初始化再在 build 里只对叶子节点赋值但我推荐显式初始化因为 pushdown 后 mul 会重置为 1、add 会重置为 0显式写清楚更容易排查状态。void build(int node, int l, int r) { mul[node] 1; add[node] 0; if (l r) { tree[node] a[l] % p; return; } int mid (l r) 1; build(node 1, l, mid); build(node 1 | 1, mid 1, r); tree[node] (tree[node 1] tree[node 1 | 1]) % p; }3.3 apply_mul 和 apply_add 两个小函数的含义我习惯把“对一个节点整体应用乘法/加法”封装成两个小函数这样 pushdown 和区间更新都能复用代码短很多。void apply_mul(int node, long long k) { tree[node] (tree[node] * k) % p; mul[node] (mul[node] * k) % p; add[node] (add[node] * k) % p; } void apply_add(int node, int l, int r, long long k) { tree[node] (tree[node] (long long)(r - l 1) * k) % p; add[node] (add[node] k) % p; }apply_mul 里add[node] (add[node] * k) % p是整份模板里最值得画线的一行。我刚才推导过整体乘 k 时节点上欠着的加法账也要放大 k 倍。少了这一行先加后乘的区间查询结果就可能出错。apply_add 里(r - l 1)是区间长度必须转成 long long 再乘 k否则两个 int 相乘可能溢出。如果 p 很大甚至tree len*k也可能超过 int所以 tree、mul、add、k 都用 long long这是最稳的写法。3.4 pushdown 的实现细节pushdown 的职责是把当前节点的懒标记下传给左右儿子。完整写法是void pushdown(int node, int l, int r) { int mid (l r) 1; int left node 1; int right node 1 | 1; if (mul[node] ! 1) { apply_mul(left, mul[node]); apply_mul(right, mul[node]); mul[node] 1; } if (add[node] ! 0) { apply_add(left, l, mid, add[node]); apply_add(right, mid 1, r, add[node]); add[node] 0; } }注意两个细节。第一先处理乘法标记再处理加法标记顺序不能反原因在 2.4 里已经讲过。第二传给左儿子和右儿子的 add 是同一个值但 apply_add 需要各自的 l、r 来计算区间长度。很多人把右儿子的区间写成(mid 1, r)却传成了(l, r)长度算多一倍输出就偏大。这类错误在模板题里非常典型。3.5 区间更新与查询的主流程区间更新分两种区间乘和区间加。它们的递归骨架完全一样区别只在完全覆盖时调用的 apply 函数不同。我建议把乘和加分开写虽然代码量多一点但读起来清楚也不容易改串。void update_mul(int node, int l, int r, int ql, int qr, long long k) { if (ql l r qr) { apply_mul(node, k); return; } pushdown(node, l, r); int mid (l r) 1; if (ql mid) update_mul(node 1, l, mid, ql, qr, k); if (qr mid) update_mul(node 1 | 1, mid 1, r, ql, qr, k); tree[node] (tree[node 1] tree[node 1 | 1]) % p; }区间加的 update_add 结构一模一样只是完全覆盖时调用 apply_add(node, l, r, k)并且要给 k 先取模。查询函数也类似遇到完全覆盖直接返回 tree[node]否则先 pushdown 再递归拼接左右结果long long query(int node, int l, int r, int ql, int qr) { if (ql l r qr) return tree[node]; pushdown(node, l, r); int mid (l r) 1; long long res 0; if (ql mid) res (res query(node 1, l, mid, ql, qr)) % p; if (qr mid) res (res query(node 1 | 1, mid 1, r, ql, qr)) % p; return res; }边界条件最容易写错的是进入左右儿子的判断。正确写法是if (ql mid)和if (qr mid)。想一想查询/更新区间 [ql, qr] 是否和左半边 [l, mid] 有交集有交集的条件是 ql mid。是否和右半边 [mid1, r] 有交集条件是 qr mid1等价于 qr mid。不要写成if (ql r)或者if (qr l)那样会多递归不需要的子树甚至无限递归。3.6 快读与取模long long、mod p 的溢出问题输入操作数有 1e5 级别用 scanf 就已经足够快没必要强行写快读。但如果刷题时习惯用 getchar 版快读也完全没问题。关键是读入乘数、加数时要用 %lld并且操作数 k 可能比 p 大很多进入更新函数前先k % p避免后面乘法溢出或者取模结果不稳定。注意如果 p 是 1k%p 会变成 0不过一般题目不会出这种极端数据真要遇到所有值对 1 取模都是 0结果也没有歧义。数据范围下long long 足够容纳中间结果n 最大 1e5每个数模 p 后不超过 2.1e9若 p 接近 int 上限区间和不超过 2.1e14乘上 k 后仍然在 long long 范围内。但如果把 tree 开成 int乘法直接溢出WA 很难查。我的习惯是只要题目涉及取模和乘法所有参与计算的变量一律 long long不要省这点内存。4. 最容易错的三个地方从报错纠错到小数据验证4.1 查询时忘记 pushdown 的典型表现查询子区间时必须调用 pushdown 把祖先节点的懒标记先结算给子节点再递归查询。否则子节点里的 tree 值还是旧的不包含祖先节点欠的账。这个 bug 的典型表现是连续做几次区间更新后查询整个区间的结果可能还对因为根节点的 tree 每次更新后立即修正了但一查询子区间结果就偏小而且偏小的规律和更新次数有关越查越明显。有一种看起来省事的做法不写 pushdown而是在查询函数里累加经过路径上的所有标记。这种方法在小规模区间加题里可行但在区间乘加的混合题里非常容易写错还要额外处理乘法对加法的缩放完全不划算。老老实实在查询的每个递归分支前先 pushdown才是模板题的正确姿势。4.2 apply_mul 没处理 add 标记一个手算反例我前面说过 apply_mul 必须同步放大 add这里给一个可以自己手算验证的反例。假设数组只有两个数 a [1, 2]。第一步给整个区间加 5根节点被打上 add5tree 变为 13子节点还没更新。第二步给整个区间乘 2根节点完整覆盖如果模板的 apply_mul 只更新 tree 和 mul不更新 add那么根节点 tree26mul2add 还是 5。这时查询整个区间的和返回 26看似正确因为 13×226。但再查询第一个数pushdown 时先把 mul2 传给左儿子左儿子 tree6×212mul2此时左儿子的 add 是 5 还是 10就决定了后续是否正确。如果 add 还是 5那么左儿子代表“原值 1 乘以 2 再加 5”等于 7而不是正确的 12如果 add 变成了 10左儿子才表示“原值 1 乘以 2 再加 10”等于 12。所以这个 bug 在只查询整段和的时候根本看不出来非得查子区间或者再做一次区间加才能暴露。P3373 的测试数据恰恰会覆盖这种情况因此一遍过的概率很低。4.3 更新边界的 if 写错导致“多更新少更新”区间更新的边界错误不像标记顺序那样隐蔽但它更常见。如果你写的是if (ql r) update(left, ...)那么当查询区间在右半边、和左半边没有交集时也会递归进左子树最终在叶子节点被ql l r qr误判为完整覆盖造成错误更新。反过来如果你写if (qr l)同样可能多走边界。另一种常见错误是把完全覆盖条件写成ql l qr r这个倒是对的但有人会写成l ql r qr也等价。最稳定的写法是先判断完全覆盖再算 mid递归时只走if (ql mid)和if (qr mid)。这样左右子树各自最多递归一次复杂度正确。4.4 小数据手算验证法n2 的两步操作调这种模板题最有效的不是瞪眼找错而是设计一组能覆盖“加乘混合”的小数据手动算好预期结果再跑程序比对。我最常用的一组是数组 [1, 2]模数取一个大数如 1000000007。操作对 [1,2] 加 5得到 [6,7]。对 [1,2] 乘 2得到 [12,14]。查询 [1,1]预期 12查询 [1,2]预期 26。如果程序输出 7 或者 13 附近的值说明 apply_mul 没有同步放大 add或者 pushdown 顺序不对。然后再补一组操作 4. 对 [1,1] 加 3得到 [15,14]。 5. 查询 [1,2]预期 29。这一步用来验证懒标记在多层之间的合并是否仍然正确。两组数据跑完模板基本就稳了。如果还不够可以继续构造先乘后加再乘再查的序列把每种组合都过一遍。4.5 调试时打印整棵树的技巧我写线段树调试时会写一个简单的 print 函数递归输出每个节点的区间、tree、mul、add。格式类似void print_tree(int node, int l, int r) { printf([%d,%d] tree%lld mul%lld add%lld\n, l, r, tree[node], mul[node], add[node]); if (l r) return; int mid (l r) 1; print_tree(node 1, l, mid); print_tree(node 1 | 1, mid 1, r); }在每次操作后调用一次把输出和手算过程对照。重点看两个地方完整覆盖后父节点的 add 和 mul 是否按照公式更新pushdown 后父节点的标记是否清零子节点的标记是否被正确叠加。很多肉眼发现不了的错误打印几行状态就一目了然。调试完记得把 print 注释掉再提交否则输出格式会乱。5. 把模板变成自己的记忆公式、扩展思路与最终模板5.1 一个公式记住合并规则如果觉得 apply_mul、apply_add、pushdown 容易记混我建议只记一个公式实际值 原始值 × 乘法标记 加法标记 × 区间长度所有标记合并规则都能从它推出整体乘 k乘法标记 ×k加法标记 ×k整体加 k加法标记 k乘法标记不动父节点下传子节点的加法先按父乘法放大再累加父加法。再配合“先乘后加”的约定你就不用死记 apply_mul 里的三行代码了。这个公式也是后续写区间赋值、区间取反等扩展题的基础会了它线段树模板就不再是一段需要背的黑盒而是可推导的工具。5.2 从“加乘”扩展到更多操作组合学会 P3373 之后“区间赋值”“区间取反”“区间 min/max 赋值”等经典扩展都可以用同样的懒标记合并思路实现。比如区间赋值相当于“先乘 0 再加 x”所以可以复用乘法加法的框架赋值标记用mul0, addx表示。区间取反则要把加和乘的合并规则反过来思考本质上还是把当前节点的懒标记整合成一个线性变换。理解了“标记是作用在子节点状态上的变换”这一层任何需要延迟更新的操作都能拆成类似的两个小函数。线段树能直接做的事远不止求和。覆盖数组最大值、最小值、区间 gcd、区间连续子段和等只要状态可以合并、懒标记可以复合都能套用同一个递归结构。P3373 是最典型的“标记复合”训练题把它吃透后面看这些扩展都会顺畅很多。5.3 线段树与树状数组模板怎么选经常有人同时刷“线段树模板”和“树状数组模板”问哪个更好。我的看法是能用树状数组解决的题目代码短、常数小、好调试比如单点修改区间求和、区间修改单点查询。但要支持区间乘区间加区间求和这种操作树状数组要么做不了要么得套差分加前缀公式推导复杂度反而不如线段树直白。所以做题时先看操作类型如果只有加法类前缀可拆分的操作优先树状数组如果涉及乘除、赋值、取反等不可简单差分的操作直接上带懒标记的线段树。P3373 属于后者模板选择没有悬念。树状数组和线段树不是二选一的死关系。它们共享“二进制划分”思想树状数组可以看成线段树的特化版本。把线段树 2 写熟之后你再看树状数组的区间修改区间求和会更容易理解差分数组为什么要那样设计。5.4 顺手收藏的常数优化与代码习惯最后分享几个我实际写题时养成的小习惯都是血的教训换来的。第一数组大小固定写N 2不要在函数里临时计算避免重复写错。第二所有和取模有关的变量统一 long long宁可多占一点内存不要因为 int 溢出换来一次 WA。第三每次读入操作数后立刻k % p这样后面所有乘法都控制在模数范围内中间结果更小、出错概率更低。第四pushdown 函数建议写成独立的函数而不是在更新函数里重复内联虽然多一次函数调用但代码清晰调试方便模板题这点开销无所谓。如果追求极致常数可以把更新和查询改成迭代版 zkw 线段树但 P3373 这种递归版足够过题没必要为了常数牺牲可读性。还有一个很多人忽略的点build 时如果输入数据全部在递归前读入那么叶子节点直接取模即可如果一边读一边 build要注意读入顺序和递归顺序一致否则会错位。保持“先读入 a 数组再 build”的写法最不容易出问题。下面是整理好的完整模板build、apply_mul、apply_add、pushdown、update 和 query 都放在一起main 里按操作类型调用直接提交即可#include bits/stdc.h using namespace std; typedef long long ll; const int N 100005; ll a[N]; ll tree[N 2], mul[N 2], add[N 2]; int n, m, p; void build(int node, int l, int r) { mul[node] 1; add[node] 0; if (l r) { tree[node] a[l] % p; return; } int mid (l r) 1; build(node 1, l, mid); build(node 1 | 1, mid 1, r); tree[node] (tree[node 1] tree[node 1 | 1]) % p; } void apply_mul(int node, ll k) { tree[node] (tree[node] * k) % p; mul[node] (mul[node] * k) % p; add[node] (add[node] * k) % p; } void apply_add(int node, int l, int r, ll k) { tree[node] (tree[node] (ll)(r - l 1) * k) % p; add[node] (add[node] k) % p; } void pushdown(int node, int l, int r) { int mid (l r) 1; int left node 1; int right node 1 | 1; if (mul[node] ! 1) { apply_mul(left, mul[node]); apply_mul(right, mul[node]); mul[node] 1; } if (add[node] ! 0) { apply_add(left, l, mid, add[node]); apply_add(right, mid 1, r, add[node]); add[node] 0; } } void update_mul(int node, int l, int r, int ql, int qr, ll k) { if (ql l r qr) { apply_mul(node, k); return; } pushdown(node, l, r); int mid (l r) 1; if (ql mid) update_mul(node 1, l, mid, ql, qr, k); if (qr mid) update_mul(node 1 | 1, mid 1, r, ql, qr, k); tree[node] (tree[node 1] tree[node 1 | 1]) % p; } void update_add(int node, int l, int r, int ql, int qr, ll k) { if (ql l r qr) { apply_add(node, l, r, k); return; } pushdown(node, l, r); int mid (l r) 1; if (ql mid) update_add(node 1, l, mid, ql, qr, k); if (qr mid) update_add(node 1 | 1, mid 1, r, ql, qr, k); tree[node] (tree[node 1] tree[node 1 | 1]) % p; } ll query(int node, int l, int r, int ql, int qr) { if (ql l r qr) return tree[node]; pushdown(node, l, r); int mid (l r) 1; ll res 0; if (ql mid) res (res query(node 1, l, mid, ql, qr)) % p; if (qr mid) res (res query(node 1 | 1, mid 1, r, ql, qr)) % p; return res; } int main() { scanf(%d%d%d, n, m, p); 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 l, r; ll k; scanf(%d%d%lld, l, r, k); update_mul(1, 1, n, l, r, k % p); } else if (op 2) { int l, r; ll k; scanf(%d%d%lld, l, r, k); update_add(1, 1, n, l, r, k % p); } else { int l, r; scanf(%d%d, l, r); printf(%lld\n, query(1, 1, n, l, r)); } } return 0; }如果你也想省事建议把这份代码整理成自己的风格而不是直接背网上的版本——自己动手抄一遍、调一遍记忆深度完全不一样。之后遇到区间加乘混合题先复制出来再根据题目微调即可。