刚刷完洛谷的 P1438《无聊的数列》这题名字起得挺有意思题目本身也确实“无聊”——一个数列两种操作一个区间加等差数列一个单点查询。但真正动手写的时候发现线段树 双懒标记这套组合并不像表面看起来那么轻松尤其是右儿子的“首项平移”那一步一句话就能让人 debug 一整晚。这篇文章把完整思路、代码实现、还有我踩过的坑全部整理出来适合两种人看一个是刚学会线段树、想搞明白懒标记怎么玩的新手另一个是用差分树状数组 AC 了、但想看双懒标记怎么“硬刚”这题的刷题党。1. 拆题P1438 到底在干什么1.1 两个操作一个查询题目维护一个长度为 n 的数列初始值都给好了后面有 m 次操作。操作一共两种1 l r k d把区间[l, r]的每个数加上一个等差数列首项是k公差是d。注意数列的起点是l所以位置i增加的值是k (i - l) * d。2 x查询数列第x个位置的当前值。n 和 m 都在十万级别最朴素的做法是每次 O(n) 地遍历区间修改查询 O(1)总复杂度 O(nm)显然过不了。凡是这种“区间改、单点查”的题脑子的第一反应基本都是差分。1.2 差分这道题的“正义解法”差分思路其实非常漂亮。假设维护一个差分数组b原数组a[i]等于差分数组的前缀和b[1] ... b[i]。那么一次区间加等差数列可以拆成三段差分修改在l这个位置加上首项k在区间[l 1, r]每个位置加上公差d在r 1这个位置减去最终的末项加首项的补偿值也就是减去k (r - l) * d。这样操作 1 变成了单点加和一个区间加常数操作 2 变成了查询前缀和。用树状数组维护两个 BIT一个管常数项一个管公差代码可以写得非常短。这种做法几乎是“标准答案”网上能搜到一堆。1.3 为什么还要线段树加双懒标记既然差分 树状数组这么香为什么还要用线段树说实话单就 P1438 这一题来讲树状数组确实更简洁。但线段树加双懒标记有它不可替代的价值思路更统一。线段树把“对整个区间打一个等差数列标记”这件事直接写在了节点上理解了这个模型以后遇到更复杂的区间修改问题就能复用。扩展性更强。如果题目改成区间求和树状数组可能还要再加辅助数组而线段树只要在节点里多维护一个sum加一段等差数列求和公式就行不用换数据结构。练习价值高。双懒标记是懒标记体系里比较经典的一种形态搞懂它后面看更复杂的“标记合并”会顺畅很多。所以本文选择用线段树 双懒标记来解这题也顺便分析一下这套做法的核心难点。2. 双懒标记的核心原理2.1 节点记录的是什么普通的区间加法懒标记节点上只需要一个add表示“这个区间整体加了多少”。但是等差数列不是整体加它加在每个位置上的值是随位置线性变化的。那单靠一个标记肯定不够。一个等差数列由两个参数决定首项和公差。所以双懒标记就是一个节点上同时维护两个增量参数add表示以当前节点区间左端点为起点这个等差数列的首项。delta表示这个等差数列的公差。比如当前节点覆盖区间[l, r]我们给它打上一个加等差数列标记意思是区间内每个位置i最终要额外增加add (i - l) * delta。注意这里的add不是通常说的“统一加多少”而是“当前区间左端点应该加多少”。如果某个标记是来自外部操作、等差数列本身的起点是L那么落到当前节点时需要重新“换算”一次首项。这一点是整个算法的灵魂。2.2 为什么两个标记够用因为等差数列和等差数列相加结果仍然是等差数列。假设区间原来有一个首项A1、公差D1的标记现在又叠加一个首项A2、公差D2的标记那么最终效果等价于一个首项A1 A2、公差D1 D2的等差数列。这个性质保证了懒标记可以放心叠加不需要把旧的标记拆开再合并。它和“常数加常数”的懒标记本质没有区别只是把一维的数值变成了二维的首项公差组合。只要想清楚两个标记各自的语义后面 update 和 push_down 都是在这两个值上做加减法。2.3 下传时给右儿子“换首项”懒标记只有在下传到子节点时才需要特别小心。父节点覆盖区间[l, r]中点为m左儿子覆盖[l, m]右儿子覆盖[m 1, r]。父节点的标记是“以l为首项起点首项A公差D”。下传的时候左儿子的区间左端点也是l所以直接把A和D分别加到左儿子的add和delta上。右儿子的区间左端点是m 1它收到的等差数列不能原封不动地继承需要把首项换成右儿子左端点对应的值。右儿子左端点m 1在父区间中的增量是A (m 1 - l) * D。而m 1 - l正好等于左儿子区间的长度也就是(m - l 1)。所以右儿子的add要加上A lenL * D其中lenL m - l 1右儿子的delta则直接加D。我单独拿一个例子验证一下。父区间[1, 6]中点m 3父标记首项A 5公差D 3。左儿子[1, 3]的标记应该是首项 5、公差 3右儿子[4, 6]的标记应该是首项5 (4 - 1) * 3 14、公差 3。用公式5 lenL * 3lenL 3 - 1 1 3算出来也是 14。把这一步搞对双懒标记就成功了一大半。3. 完整实现线段树加双懒标记打 P14383.1 节点设计与建树既然只是单点查询节点里可以不维护区间和只维护val、add、delta三个字段。val只在叶子节点有意义保存原始数列的值add和delta是懒标记表示以当前节点左端点为起点的等差增量。建树和普通线段树基本一样走到叶子时把数组值赋给val就行。内部节点的val不需要更新因为题目不查区间和。#include bits/stdc.h using namespace std; typedef long long ll; const int N 100005; struct Node { ll val; // 叶子节点存原数组值 ll add; // 懒标记等差数列首项相对当前节点左端点 ll delta; // 懒标记等差数列公差 } tr[N 2]; ll a[N]; int n, m; void build(int p, int l, int r) { if (l r) { tr[p].val a[l]; return; } int mid (l r) 1; build(p 1, l, mid); build(p 1 | 1, mid 1, r); }3.2 区间更新 updateupdate(p, l, r, L, R, k, d)表示要给区间[L, R]加上一个首项为k、公差为d的等差数列等差数列的起点是L而不是当前递归到的l。当前区间[l, r]被更新区间[L, R]完全覆盖时可以整块打标记。但这时不能直接把k加到add上要先把首项换算成相对于当前区间左端点l的值void update(int p, int l, int r, int L, int R, ll k, ll d) { if (L l r R) { ll k0 k (ll)(l - L) * d; tr[p].add k0; tr[p].delta d; return; } push_down(p, l, r); int mid (l r) 1; if (L mid) update(p 1, l, mid, L, R, k, d); if (R mid) update(p 1 | 1, mid 1, r, L, R, k, d); }这段代码里k0 k (ll)(l - L) * d是唯一的“门道”。因为现在要打的等差数列在原目标区间L处是k而当前节点左端点是l所以当前节点左端点的实际增量就是k (l - L) * d。这样懒标记记录的就是“以当前节点左端点为起点的首项”。递归进入子区间时仍然传原始的k和d因为外部等差数列的起点L始终没变子节点在完全覆盖时会自己再换算一次首项。3.3 懒标记下传 push_downpush_down做的事情就是之前讨论的“换首项”规则。因为这里只查单点所以push_down在update和query里都要用但注意它只有在l ! r时才会被调用。inline void push_down(int p, int l, int r) { ll A tr[p].add; ll D tr[p].delta; if (A 0 D 0) return; int mid (l r) 1; int lenL mid - l 1; // 左儿子首项不变 tr[p 1].add A; tr[p 1].delta D; // 右儿子首项要平移 lenL * D tr[p 1 | 1].add A lenL * D; tr[p 1 | 1].delta D; // 清空当前节点标记 tr[p].add 0; tr[p].delta 0; }这里有个容易绕晕的点左儿子区间的长度是lenL右儿子左端点相对父节点左端点的偏移是mid 1 - l而它正好也等于lenL所以右儿子的首项平移量用的是lenL * D。每次重写这一句的时候我都习惯在草稿纸上画一棵区间树不然很容易写成(r - mid)或者(mid - l)。3.4 单点查询 query单点查询的思路是从根一路走到目标叶子每次进入儿子之前先把父节点的懒标记下传。这样所有祖先曾经打过的等差数列标记最终都会一级一级落到目标叶子节点的add上。到了叶子直接返回tr[p].val tr[p].add。ll query(int p, int l, int r, int x) { if (l r) { return tr[p].val tr[p].add; } push_down(p, l, r); int mid (l r) 1; if (x mid) return query(p 1, l, mid, x); return query(p 1 | 1, mid 1, r, x); }叶子节点的delta可能有值但单点位置不存在“后面的元素”所以查询时不加delta只加add。这个处理在逻辑上非常统一只要保证每次push_down都把正确的首项传到了叶子叶子add就代表最终增量。3.5 完整代码把上面的函数拼起来加上主函数读入输出就是可以直接提交的完整版本#include bits/stdc.h using namespace std; typedef long long ll; const int N 100005; struct Node { ll val; ll add; ll delta; } tr[N 2]; ll a[N]; int n, m; void build(int p, int l, int r) { if (l r) { tr[p].val a[l]; return; } int mid (l r) 1; build(p 1, l, mid); build(p 1 | 1, mid 1, r); } inline void push_down(int p, int l, int r) { ll A tr[p].add; ll D tr[p].delta; if (A 0 D 0) return; int mid (l r) 1; int lenL mid - l 1; tr[p 1].add A; tr[p 1].delta D; tr[p 1 | 1].add A lenL * D; tr[p 1 | 1].delta D; tr[p].add 0; tr[p].delta 0; } void update(int p, int l, int r, int L, int R, ll k, ll d) { if (L l r R) { ll k0 k (ll)(l - L) * d; tr[p].add k0; tr[p].delta d; return; } push_down(p, l, r); int mid (l r) 1; if (L mid) update(p 1, l, mid, L, R, k, d); if (R mid) update(p 1 | 1, mid 1, r, L, R, k, d); } ll query(int p, int l, int r, int x) { if (l r) { return tr[p].val tr[p].add; } push_down(p, l, r); int mid (l r) 1; if (x mid) return query(p 1, l, mid, x); return query(p 1 | 1, mid 1, r, x); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m; for (int i 1; i n; i) cin a[i]; build(1, 1, n); while (m--) { int op; cin op; if (op 1) { int l, r; ll k, d; cin l r k d; update(1, 1, n, l, r, k, d); } else { int x; cin x; cout query(1, 1, n, x) \n; } } return 0; }这段代码的时间复杂度是 O((n m) log n)每棵线段树节点信息量很固定内存占用大概是4 * N * 24字节十万数据下非常宽裕。4. 踩坑记录与自查方法4.1 右儿子的首项平移公式错一个符号就全乱这个坑绝对是最常见的。push_down里右儿子的add是A lenL * D但我见过不少写法写成了A (mid - l) * D、A (r - mid) * D甚至直接写成了A D。为什么会错因为很多人没有意识到右儿子的区间左端点是mid 1它到父节点左端点l的距离是mid 1 - l而lenL mid - l 1两者相等。这里差一个 1加上去之后首项就不对。哪怕首项只差一个公差最终单点查询的值也会错得离谱。比较有效的自查方法是找一个长度是偶数的区间比如父区间[1, 4]mid 2lenL 2。父标记首项A、公差D右儿子左端点是3它的首项应该是A (3 - 1) * D A 2D正好等于A lenL * D。如果写成A (mid - l) * D A D一眼就能看出少了。4.2 update 完全覆盖之前要不要先 push_down很多初学懒标记的人会纠结update函数里是应该先判完全覆盖还是先push_down正确顺序一定是先判完全覆盖能直接打标记就直接打别先下传。因为一个节点已经有一个等差数列懒标记这时候如果新的操作也完全覆盖这个节点直接把新首项、新公差叠加到旧标记上就完事了完全没必要把旧标记先递给儿子。但如果当前区间没有被完全覆盖那就必须先把父节点的懒标记下传再递归修改子节点。否则子节点在修改时看不到祖先已经打下的标记后续合并顺序会乱。这个“按需下传”的思想是懒标记的精髓一定要养成肌肉记忆。4.3 只用一个懒标记为什么不够有同学可能会想能不能不用delta只在节点上存一个add表示这段区间第一个位置增加了多少然后查询的时候再自己乘位置不行。因为懒标记下传到子节点时如果只有一个add左、右儿子都不知道公差是多少右儿子无法换算新首项。更直接地说等差数列是二维信息一个标量存不下。把它想成线性函数你就明白了add (i - l) * delta就是一串关于位置i的线性函数首项是截距公差是斜率。要完整描述一条直线截距斜率都要有。所以双懒标记不是“线段树需要两个标记”而是“线性变化本身就自带两个自由度”。4.4 long long 与数组大小的教训P1438 的数据范围我记得不是特别苛刻但等差数列叠加几十万次以后中间值很容易超过int。比如每次d 100000区间长度十万里累加随便就上亿了。所以add、delta、k、d以及计算k0时乘出来的临时值全部用long long最稳妥。数组大小开N 2也就是4 * N这个是线段树的铁律。开2 * N大概率会越界但越界不一定报 RE有时候会静默访问到别的数组最后查出来是一个完全没关系的变量被改掉了。这个坑最阴。4.5 小数据手工对拍法调试这题最管用的方法不是盯代码而是拿小数据手算。比如n 5初始数组1 2 3 4 5操作1 2 4 1 2表示给[2, 4]加上首项 1、公差 2所以位置 2 加 1位置 3 加 3位置 4 加 5。查pos3答案应该是3 3 6。自己先把答案算出来再跑代码。如果答案不对就在update和push_down里分别打印每个节点add和delta一步一步跟着递归走基本能定位到是哪个括号少了。我在写这题的时侯靠这个方法抓到的 bug 几乎全是右儿子首项平移公式的问题。5. 扩展如果题目改成区间求和怎么办5.1 节点里多维护一个 sumP1438 只要求单点查询所以节点可以不维护区间和。但双懒标记的价值在于它完全可以扩展到区间查询。只要在节点中多维护一个sum表示当前区间的实际总和然后在打懒标记和push_down的时候同步更新sum就行。具体来说节点覆盖长度为len如果给它加上一个以当前节点左端点为起点、首项为A、公差为D的等差数列那么整个区间总和会增加len * A D * len * (len - 1) / 2这个公式本质是等差数列求和。首项是 A末项是 A (len - 1) * D和就是len * (首项 末项) / 2展开就是这个式子。5.2 给双懒标记做加法求和push_down时也要同步更新儿子的sum。左儿子区间长度lenL直接套公式右儿子区间长度lenR先把首项平移成B A lenL * D再用 B 带入公式。这个扩展写下来代码会比单点查询版长不少但核心的双懒标记逻辑一模一样。只要理解了“等差数列求和公式 首项平移”从单点版改成区间求和版其实非常流水线。这也是为什么我推荐学这题时不要直接抄差分模板而是踏踏实实把线段树这个版本写一遍。5.3 我的最终体会刷完 P1438我对懒标记有了新的理解懒标记本质上不是在“偷懒”而是在节点粒度上维护一个变换。普通区间加是“同一个常数变换”等差数列是“一个线性变换”以后可能还会遇到更复杂的变换但只要变换满足结合律、能快速合并、能批量作用到区间和上线段树就能支持。回到这一题虽然差分加树状数组是更优解但线段树加双懒标记给我带来的收获其实更大。至少以后再看到“区间加等差数列”这种字眼我脑子里会立刻浮现出add和delta两个标记以及右儿子首项平移那个细节。这大概就是刷题的意义AC 不是终点把每一个标记的来龙去脉都搞明白才是。