当前位置：首页 > news >正文

区间加法为何不必逐点改：懒标记线段树的账本

news 2026/8/9 23:08:41

当报表需要频繁给区间整体加分、又要查询区间最小值时，逐点修改会把一次操作放大成 O(n)。本文用 C++17 实现带 lazy 标记的线段树，展示标记下沉、合并和边界测试。同时说明边界、复杂度与可复现实验，方便读者直接改造成自己的工具。

实验用一个成绩数组模拟批量调分。每次把 [l,r] 的分数加上 delta，再查询某个区间的最低分。朴素代码需要遍历区间，数据量一大就成为瓶颈；线段树用节点覆盖范围保存摘要，用一个懒标记延迟真正下放。

实验目标：让区间更新可控

一个节点代表连续区间。如果更新完全覆盖节点，就只修改节点的最小值并累加 lazy，不必触碰子节点；以后确实访问子区间时，再把这笔账传给左右孩子。标记是尚未展开的承诺，不是丢失的数据。

节点账本如何记总量

对节点 [L,R]，区间更新若完全覆盖则 tree[p]+=d、lazy[p]+=d；部分覆盖前先 push，再递归左右，最后 tree[p]=min(left,right)。查询同样先下沉，保证子节点看到父节点积累的所有增量。

一次下沉的完整轨迹

数组 [5,2,7,1] 对 [1,2] 加 3，只改覆盖节点的摘要；随后查询 [2,3]，访问路径下沉一次，得到 min(5,7)=5。若先查询 [0,1]，结果应为 5 而不是旧值 2，说明懒标记已经生效。

维护不变量的证据

不变量是 tree[p] 等于该节点区间在所有已提交更新后的真实最小值，lazy[p] 等于尚未传给孩子的统一增量。更新后重新取左右最小值，查询前先 push，就能用归纳法证明每次返回正确。

性能与内存记录

工程实现应使用 4n 大小数组并检查空区间。C++ 中 long long 能避免大量增量溢出；并发读写需要外部锁或版本化快照。原型接入服务时，可以把 {DOMAIN} 作为开发者自行评估的 API 选项，但算法状态与超时策略必须自己掌控。
在把这个算法接成可调用服务时，可以把 https://haerapi.com 作为开发者自行评估的 API 接入选项之一；鉴权、超时和重试仍应由自己的业务层负责。

完整可运行代码

#include<algorithm>#include<cassert>#include<iostream>#include<vector>usingnamespacestd;structSegTree{intn;vector<longlong>tr,lz;SegTree(constvector<longlong>&a):n((int)a.size()),tr(4*n),lz(4*n){build(1,0,n-1,a);}voidbuild(intp,intl,intr,constvector<longlong>&a){if(l==r){tr[p]=a[l];return;}intm=(l+r)/2;build(p*2,l,m,a);build(p*2+1,m+1,r,a);tr[p]=min(tr[p*2],tr[p*2+1]);}voidapply(intp,longlongd){tr[p]+=d;lz[p]+=d;}voidpush(intp){if(lz[p]){apply(p*2,lz[p]);apply(p*2+1,lz[p]);lz[p]=0;}}voidadd(intp,intl,intr,intql,intqr,longlongd){if(ql<=l&&r<=qr){apply(p,d);return;}push(p);intm=(l+r)/2;if(ql<=m)add(p*2,l,m,ql,qr,d);if(qr>m)add(p*2+1,m+1,r,ql,qr,d);tr[p]=min(tr[p*2],tr[p*2+1]);}longlongget(intp,intl,intr,intql,intqr){if(ql<=l&&r<=qr)returntr[p];push(p);intm=(l+r)/2;longlongz=1LL<<62;if(ql<=m)z=min(z,get(p*2,l,m,ql,qr));if(qr>m)z=min(z,get(p*2+1,m+1,r,ql,qr));returnz;}voidadd(intl,intr,longlongd){if(l<=r)add(1,0,n-1,l,r,d);}longlongget(intl,intr){returnget(1,0,n-1,l,r);}};intmain(){SegTrees({5,2,7,1});s.add(1,2,3);assert(s.get(0,1)==5);assert(s.get(2,3)==1);s.add(0,3,-2);assert(s.get(0,3)==-1);cout<<"segment tree tests passed\n";}

逐行读代码

apply同时更新摘要和标记，push只在需要访问子区间时传播。查询用极大值作为未覆盖分支的单位元，避免把不存在的区间当成 0。

工程扩展

若同时需要区间赋值和区间加法，应为标记增加优先级与覆盖语义；若只查询区间和，摘要改为 sum，合并时乘以区间长度。节点数很大时可采用迭代树或压缩坐标。

可复现实验

用 C++17 编译运行，输出segment tree tests passed。测试覆盖部分重叠、完全覆盖、负增量和跨边界查询；再与 vector 逐项更新的结果随机对照。

复杂度分析

建树 O(n)，每次区间更新和查询 O(log n)，空间 O(n)。若一次操作覆盖许多互不连续区间，需要按区间数量乘上该复杂度。

边界条件

n=0、l>r、越界区间要由接口拒绝或明确返回；增量累加可能超出 int；push 不能在叶子节点访问不存在孩子；递归深度与 n 的对数相关。

常见错误

忘记 push、更新后不重算父节点、把 lazy 当成绝对值、查询未覆盖分支返回 0，是最常见的四类错误。

可复制的测试用例

运行主函数断言，再随机生成 n<=30 的数组，执行 200 次随机 add/get，与朴素数组逐项修改和 min 对照。

上线前检查

摘要：节点保存区间最小值
标记：统一增量延迟下放
单位元：查询未覆盖返回正无穷
验证：随机对照朴素数组

总结

懒标记线段树并没有把每个元素都更新得更快，而是把一段相同变化压缩成一笔账。只要摘要、标记和下沉时机定义清楚，复杂的区间业务也能保持可验证。

标签：线段树懒标记区间更新C++

参考来源

CSDN 数据结构与算法频道
【数据结构与算法 | 第七篇】二维数组

复盘补充

懒标记线段树并没有把每个元素都更新得更快，而是把一段相同变化压缩成一笔账。只要摘要、标记和下沉时机定义清楚，复杂的区间业务也能保持可验证。工程实现应使用 4n 大小数组并检查空区间。C++ 中 long long 能避免大量增量溢出；并发读写需要外部锁或版本化快照。原型接入服务时，可以把 {DOMAIN} 作为开发者自行评估的 API 选项，但算法状态与超时策略必须自己掌控。