洛谷 P1438《无聊的数列》名字起得挺谦虚实际上是我见过最适合讲清楚“线段树双懒标记”的一题。题目要求区间加等差数列再单点查值。很多人第一反应是拿普通线段树硬上懒标记里只存一个“加了多少”遇到等差数列就傻眼因为区间内每个位置加的数不一样根本没法用一个数表示。这题我最早是用差分过的后来重新整理模板时把“首项公差”的双懒标记写法也想明白了才发现它才是真正把等差数列和线段树结构结合起来的思路。这篇博文把两条路都讲清楚重点放在双懒标记的坐标系变换上代码也贴完整版方便直接抄走。1. 题目在问什么为什么“只加一个数”的懒标记不行1.1 原题操作拆解P1438 的题面很干净长度为 n 的数组两种操作。第一种是修改给定 l、r、k、d要求把区间 [l, r] 内第 i 个位置从 l 开始数加上首项为 k、公差为 d 的等差数列位置 l 加 k位置 l1 加 kd位置 l2 加 k2d以此类推直到位置 r 加 k(r-l)d第二种是查询给定 x输出当前数组第 x 个位置的值。n 和操作数都在 1e5 级别也就是说暴力修改单点不可行一次操作至少要压到 O(logn) 才有救。最自然的想法是线段树。但这里有个关键障碍经典的线段树懒标记通常存一个“常数偏移”pushdown 的时候直接把同一个数值传给左右儿子。等差数列可不是常数偏移区间内每个位置要加的值都不一样一个普通的 int 根本装不下这种“带斜率”的增量。那是不是可以在线段树节点里多存几个数来表示这个等差数列可以这就是双懒标记。一个节点上记录“首项”和“公差”代表这个区间整体被加了一个等差数列。两个等差数列叠在一起结果仍然是等差数列首项相加、公差相加所以懒标记可以正常合并。这条思路的核心难点只有一个不同节点的懒标记基准位置不一样怎么统一。1.2 数据范围决定思路再补充一下复杂度预期。1e5 的数据量线段树 O(logn) 单次操作完全够用递归常数也能接受。如果用差分思路还需要把原数组转化为差分数组本质上也是把等差数列变成常数操作同样在 O(logn) 内解决问题。两条路线的难度都不算高难的是第一次接触时“怎么把等差数列翻译成线段树能维护的信息”。这也是为什么这道题在洛谷上是提高/省选- 难度算法本身不冷门但思维拐弯比较隐蔽。我见过不少选手卡在这里看题解能看懂自己写就总差一点十有八九是没把“每个节点上的懒标记到底代表什么”想清楚。2. 双懒标记的核心首项、公差以及坐标系的统一2.1 懒标记的定义先规定线段树节点 p 对应区间 [L, R]。节点上有两个懒标记addA[p]首项标记addD[p]公差标记含义是这个区间内每个位置 ii ∈ [L,R]相对于初始值还要额外增加addA[p] (i - L) * addD[p]也就是说addA[p] 表示“区间左端点 L 这个位置需要加多少”addD[p] 表示“往右走一步增量增加 addD[p]”。这样任意一个位置 i 的附加量都能用一次乘法算出来。为什么一定要定义成“相对于本区间左端点 L”因为懒标记要合并。如果两个等差数列都相对于同一个左端点 L那么直接相加首项和公差即可。如果第一个相对于左端点 L第二个相对于修改区间的左边界 ql那相加前必须先换算。统一使用“本区间左端点”作为基准可以保证同一个节点上的多个懒标记永远可以直接相加不用考虑什么优先级关系。2.2 一次区间修改如何落到节点上假设现在有一个修改操作给 [ql, qr] 加首项 k、公差 d。对于任意被完整覆盖的节点 [L, R]区间里位置 i 的增量为k (i - ql) * d我要把这个表达式改写成上面懒标记的形式A (i - L) * D把 i 提取出来对比一下两边k (i - ql) * d (k (L - ql) * d) (i - L) * d所以新首项 A k (L - ql) * d新公差 D d这里 A 的计算是整道题最关键的公式也是最容易写错的地方。(L - ql) 表示该节点左端点相对于修改区间左端点的偏移量乘上公差 d得到“如果把等差数列左端点搬到自己这个区间的左端点上首项应该是多少”。代码里就一行ll A k (L - ql) * d; lazyA[p] A; lazyD[p] d;注意这里用的是 L不是 l 也不是 1。我见过不少初学者把这个地方写成 k (l - ql) * d然后对着样例怎么调都对不上因为当前节点区间左端点不是查询区间的左端点。2.3 为什么懒标记可以直接合并假设节点 [L,R] 已经被叠加过 j 个等差数列每个都换算成了相对于 L 的 (A_j, D_j)。现在又来一个 (A, D)。由于对所有 i ∈ [L,R]∑(A_j (i-L)D_j) (∑A_j) (i-L)(∑D_j)新的附加总量仍然是一个等差数列形式完全一致。所以懒标记合并就是简单加法没有复杂的先后顺序问题。这也是双懒标记比“加法/乘法双懒标记”舒服的地方——涉及乘法时懒标记要有优先级还要考虑历史值因为乘法对加法有分配律。这里全是加法而且是“带梯度的加法”本质还是加法合并零压力。所以可以这样理解普通懒标记是两位一体里的“常数部分”双懒标记只是额外多了一位“斜率”。因为等差数列的加法封闭性足够好才能这么玩。如果题目改成区间加等比数列两个等比数列相加的结果不再是等比数列懒标记就没法直接合并了那就是另一套完全不同的思路。2.4 顺带推导一下区间和公式如果题目从单点查询扩展成区间查询光有懒标记不够还得维护一个 sum[p]表示当前区间实际值的和。节点 [L,R] 的懒标记是 (A, D)长度为 len R-L1那么这个节点覆盖的所有位置附加增量之和是len * A D * (0 1 ... (len-1))化简一下就是len * A D * len * (len-1) / 2这个公式在 pushdown 时要反复用到。虽然 P1438 原题只需要单点查询但既然讲了双懒标记就顺手把 pushdown 需要的公式一起推了后面扩展部分直接用。3. 完整代码与关键函数逐段拆解3.1 数据结构与主流程因为 P1438 只要求单点查询代码可以做到非常短不需要 sum、不需要 pushup、不需要 pushdown。你只需要在 update 的时候把懒标记累加到被完整覆盖的节点上查询的时候把路径上所有节点的懒标记对 x 的贡献加起来。这其实是懒标记“完全不下传”的形态反而最不容易错。#include bits/stdc.h using namespace std; typedef long long ll; const int MAXN 100005; int n, m; ll a[MAXN]; ll lazyA[MAXN 2]; // 首项懒标记 ll lazyD[MAXN 2]; // 公差懒标记 void update(int p, int l, int r, int ql, int qr, ll k, ll d) { if (ql l r qr) { // 当前节点区间 [l, r] 内位置 i 的增量为 k (i - ql) * d // 转化为相对于当前节点左端点 l 的表示A (i - l) * D ll A k (l - ql) * d; lazyA[p] A; lazyD[p] d; return; } int mid (l r) 1; if (ql mid) update(p 1, l, mid, ql, qr, k, d); if (qr mid) update(p 1 | 1, mid 1, r, ql, qr, k, d); // 注意这里不需要 pushup因为我们没有维护任何区间聚合信息 } ll query(int p, int l, int r, int x, ll acc) { // 当前节点 [l, r] 上的懒标记对位置 x 的贡献 acc lazyA[p] (x - l) * lazyD[p]; if (l r) return a[x] acc; int mid (l r) 1; if (x mid) return query(p 1, l, mid, x, acc); else return query(p 1 | 1, mid 1, r, x, acc); } int main() { scanf(%d%d, n, m); for (int i 1; i n; i) scanf(%lld, a[i]); while (m--) { int op; scanf(%d, op); if (op 1) { int l, r; ll k, d; scanf(%d%d%lld%lld, l, r, k, d); update(1, 1, n, l, r, k, d); } else { int x; scanf(%d, x); printf(%lld\n, query(1, 1, n, x, 0)); } } return 0; }这段代码在洛谷 P1438 上可以 AC空间 O(n)每次操作 O(logn)。我测试过 nm1e5 的随机数据运行时间大约在几十毫秒级别完全没有性能压力。3.2 update 为什么不 pushup很多刚学线段树的朋友看到这里会疑惑updata 修改了子节点为什么父节点不重新算 sum原因很简单这个版本里线段树节点根本没有 sum 字段。我维护的不是“区间和”而是“区间懒标记”。每次区间操作只是往节点上叠一个 (A, D)并没有任何聚合信息需要向上传递。换句话说这个写法把线段树当成了一棵“可分裂的索引树”修改时把等差数列按线段树的区间划分存到若干个互不重叠的节点上查询时从根到叶子累加所有经过节点的懒标记。因为懒标记一旦存在就不会向下传也不会向上合并所以它的生命周期就是“在节点上躺着直到查询把它读出来”。这比带 pushdown 的写法更贴合“只单点查”的应用场景。如果哪一步你想到要 pushup 了说明你已经开始同时维护 sum 这类聚合信息。只要你维护了聚合信息就必须 pushup否则父节点的 sum 会漏掉子节点刚发生的修改。这里没有 sum所以不需要。3.3 query 的路径累加为什么是可行的查询位置 x 时函数携带了一个 acc 参数表示“从根节点到当前节点父节点为止已经累计了多少增量”。每一次进入节点 p就把 p 自身的懒标记对 x 的贡献累加到 accacc lazyA[p] (x - l) * lazyD[p]这里 (x - l) 是 x 相对于当前节点左端点的偏移。因为懒标记的基准是“本区间左端点”所以这个偏移乘公差就是额外的贡献。当递归到叶子时答案就是原始 a[x] 加上 acc。这个过程不会重复累加因为每个节点的懒标记只被访问一次也不会漏掉因为所有覆盖 x 的区间修改最终都会落在根到叶子的某条路径上的若干节点里这些节点全部会被经过。举个小例子第一次给 [1,4] 加首项 1 公差 1第二次给 [3,4] 加首项 10 公差 2。第一二次修改时[1,4] 会被拆成 [1,2] 和 [3,4] 两个节点。查询 x3 时路径经过 [1,4]、[3,4]、[3,3]两个修改分别存在 [1,2] 和 [3,4] 上。因为 x3 不在 [1,2] 里所以查询路径不会经过 [1,2]第一个等差数列对 x3 的贡献不会被错误累加。但第二个等差数列存在 [3,4] 上路径正好经过它于是贡献被正确加上。这就是“查询路径与覆盖区间交集为零的部分恰好不会被访问”的直观解释。4. 另一种经典做法差分 普通懒标记4.1 差分转换的推导P1438 还有一种非常主流的做法差分数组。设 b[i] a[i] - a[i-1]特别地 b[1] a[1]。这样原数组的第 x 个位置就等于 b[1] 到 b[x] 的前缀和。现在给 [l, r] 加上首项 k、公差 d 的等差数列。观察相邻两项差分的变化在 l 处a[l] 增加了 k所以 b[l] k对 l1 到 r 的每个位置 ia[i] 和 a[i-1] 都分别增加了不同的值但差值固定为 d所以 b[l1] 到 b[r] 都 d在 r1 处a[r1] 不增加而 a[r] 增加了 k(r-l)d所以 b[r1] - (k(r-l)d)于是一次区间加等差数列被拆成了三次“普通区间加常数”的操作。线段树上只需要一个懒标记维护区间和再支持区间加和区间求和前缀和就是区间求和的特例就能解决 P1438。这个思路的优点是懒标记只有一个线段树模板不用改很多人因为熟悉普通线段树所以觉得差分更稳妥。缺点是要多处理一个差分边界并且修改操作从一次 update 变成最多三次 update。4.2 差分版完整代码#include bits/stdc.h using namespace std; typedef long long ll; const int MAXN 100005; int n, m; ll a[MAXN]; ll sum[MAXN 2], lazy[MAXN 2]; void build(int p, int l, int r) { if (l r) { sum[p] a[l] - a[l - 1]; return; } int mid (l r) 1; build(p 1, l, mid); build(p 1 | 1, mid 1, r); sum[p] sum[p 1] sum[p 1 | 1]; } void pushdown(int p, int l, int r) { if (!lazy[p]) return; int mid (l r) 1; sum[p 1] lazy[p] * (mid - l 1); sum[p 1 | 1] lazy[p] * (r - mid); lazy[p 1] lazy[p]; lazy[p 1 | 1] lazy[p]; lazy[p] 0; } void update(int p, int l, int r, int ql, int qr, ll v) { if (ql qr) return; if (ql l r qr) { sum[p] v * (r - l 1); lazy[p] v; return; } pushdown(p, l, r); int mid (l r) 1; if (ql mid) update(p 1, l, mid, ql, qr, v); if (qr mid) update(p 1 | 1, mid 1, r, ql, qr, v); sum[p] sum[p 1] sum[p 1 | 1]; } ll query(int p, int l, int r, int ql, int qr) { if (ql l r qr) return sum[p]; pushdown(p, l, r); int mid (l r) 1; ll ans 0; if (ql mid) ans query(p 1, l, mid, ql, qr); if (qr mid) ans query(p 1 | 1, mid 1, r, ql, qr); return ans; } 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 l, r; ll k, d; scanf(%d%d%lld%lld, l, r, k, d); update(1, 1, n, l, l, k); update(1, 1, n, l 1, r, d); if (r 1 n) update(1, 1, n, r 1, r 1, -(k (r - l) * d)); } else { int x; scanf(%d, x); printf(%lld\n, query(1, 1, n, 1, x)); } } return 0; }这里有一个容易忽略的边界当 r1 n 时才执行第三个 update。原数组最后一个元素后面没有差分元素如果 r n直接对 n1 位置更新就会越界。update 函数虽然对 ql qr 做了保护但对 r1 n 的情况没有任何保护。4.3 两种做法对比对比项差分 普通懒标记双懒标记不下传版维护对象差分数组原数组懒标记数量1 个区间加2 个首项、公差每次区间修改2 到 3 次 update1 次 update单点查询方式前缀和路径累加思维难点差分构造首项坐标变换需要 pushdown需要不需要代码量稍长很短我个人的体感差分法适合“只求 AC、不想冒险”的人因为它每一步都是熟脸操作双懒标记法适合“想把线段树玩明白”的人因为它逼着你理解懒标记的几何意义。两道题做完你会发现很多区间的“特殊增量”题解法都离不开“统一基准”这四个字。5. 踩坑记录、对拍技巧与扩展5.1 常见错误速查表写这道题时我前后踩过不少坑整理成表格放在这里覆盖了新手最容易出问题的几个点症状为什么发生怎么修样例能过提交 WA答案偏差非常规律懒标记首项没有按节点左端点换算直接用 k 和 d重新按 A k (L-ql)*d 计算相邻位置的增量是对的整体起点偏了公差 D 正确但首项 A 丢了 (L-ql)*d检查坐标变换不要漏偏移查询结果越改越大像把所有历史操作加了两三遍在递归里重复累加了祖先节点的懒标记用 acc 参数每层只加一次当前节点差分写法下标越界r n 时还更新 r1 位置加 if (r 1 n) 判断答案负数/异常大数据范围超出 int但没有用 long long所有数值存储统一用 ll双懒标记版本写上了 pushup结果部分修改被覆盖没有维护 sumpushup 没有意义不下传版本直接删掉 pushup第六行值得多说一句。如果你在看别人代码时发现既有 lazyA/lazyD 又有 sum还带着 pushup那是完整支持区间查询的写法不是错的。但如果你只是做 P1438 单点查询却把完整模板硬搬过来容易在极简和完整之间出现逻辑混乱。建议选择一种思路写到底。5.2 自测与对拍方法这题有一个非常好的自测手段写一个暴力程序同一组数据下逐行比对答案。暴力程序非常简单void brute_add(int l, int r, ll k, ll d) { for (int i l; i r; i) a[i] k (i - l) * d; } ll brute_query(int x) { return a[x]; }然后写一个数据生成器n 取 5 到 30m 取 50 到 200随机生成操作。这里分享一个小技巧生成等差数列时k 和 d 不要总取正数带点负数才更容易暴露坐标变换问题。生成器把操作同时写入“标准程序”和“待测程序”标准程序用暴力跑待测程序用线段树跑最后逐行 diff。Linux 环境下对拍脚本可以这样写while true; do ./gen in.txt ./std in.txt out1.txt ./sol in.txt out2.txt diff out1.txt out2.txt || break doneWindows 用户也可以用简单的循环加 fc 命令。实测下来只要随机数据对拍过几千组代码基本不会出隐藏问题。我当年写双懒标记版第一版就是因为 A 的公式写错用 200 组随机数据一下子就把问题暴露出来了。5.3 如果改成区间查询怎么办pushdown 版本有些题目会在此基础上把“单点查询”改成“区间查询”那不下传版本就不够用了因为你没法快速回答“某个区间内一共有多少增量”。此时需要维护 sum[p]并实现 pushdown。关键代码是这样void pushdown(int p, int l, int r) { if (lazyA[p] 0 lazyD[p] 0) return; int mid (l r) 1; int lenL mid - l 1; lazyA[p 1] lazyA[p]; lazyD[p 1] lazyD[p]; sum[p 1] lenL * lazyA[p] lazyD[p] * lenL * (lenL - 1) / 2; ll Aright lazyA[p] (mid 1 - l) * lazyD[p]; int lenR r - mid; lazyA[p 1 | 1] Aright; lazyD[p 1 | 1] lazyD[p]; sum[p 1 | 1] lenR * Aright lazyD[p] * lenR * (lenR - 1) / 2; lazyA[p] lazyD[p] 0; }右子节点的首项为什么是 Aright lazyA[p] (mid1-l)*lazyD[p]因为父节点区间左端点是 l右子节点左端点是 mid1中间差了 (mid1-l) 步每步增量为 lazyD[p]。这和 update 里 A 的换算公式是同一个原理。写了 pushdown 之后update 里也要在递归前后分别 pushdown 和 pushupvoid update(int p, int l, int r, int ql, int qr, ll k, ll d) { if (ql l r qr) { ll A k (l - ql) * d; int len r - l 1; sum[p] len * A d * len * (len - 1) / 2; lazyA[p] A; lazyD[p] d; return; } pushdown(p, l, r); int mid (l r) 1; if (ql mid) update(p 1, l, mid, ql, qr, k, d); if (qr mid) update(p 1 | 1, mid 1, r, ql, qr, k, d); sum[p] sum[p 1] sum[p 1 | 1]; }区间查询时也是标准的“完全覆盖就返回 sum[p]否则 pushdown 再递归左右子树”。5.4 还能怎么变双懒标记这套思路的适用范围比想象中宽。比如操作叠加上“常数加”可以看成公差为 0 的等差数列两个懒标记依旧处理。区间加等差数列 区间求和就是上一个小节写的完整版。区间加等差数列 区间取模取模不改变等差数列结构懒标记叠加以后取个模就行。区间加等差数列 单点查询原题的场景用不下传版最省代码。但注意如果题目要求区间加等比数列双懒标记就不能直接套了。原因是两个等比数列相加结果不是等比数列懒标记叠加后结构会被破坏。碰到那种题基本就要往矩阵乘法的方向想或者转换成前缀和做差再维护。这就扯远了有机会单独写一篇。最后再分享一个心得写任何带着懒标记的线段树每次在 pushdown 或 update 里做“偏移变换”时心里都要默念一句“我现在相对于哪个左端点”。这个基准捋顺了双懒标记只是名字吓人代码换汤不换药基准没捋顺样例都骗不过去。P1438 作为双懒标记的入门题把这一个点吃透后续再遇到类似“带梯度区间更新”的题目你就能一眼看出该在节点里加什么信息而不用每次都对着题解发愁。