数据结构——带懒标记的线段树

一、什么是线段树线段树是一种二叉树数据结构用于高效地处理区间查询和区间更新操作。核心思想将数组分成若干个区间线段每个节点代表一个区间通过合并子节点的信息来得到父节点的信息。适用场景区间求和、最大值、最小值区间加、区间乘、区间赋值动态统计数据二、线段树的结构以数组[1, 2, 3, 4, 5]为例[1-5] (15) / \ [1-3] (6) [4-5] (9) / \ / \ [1-2] (3) [3] (3) [4] (4) [5] (5) / \ [1] (1) [2] (2)每个节点存储区间范围该区间的信息如和、最大值等懒标记可选用于区间更新优化例题洛谷P3372题目描述如题已知一个数列 {ai​}你需要进行下面两种操作将某区间每一个数加上 k。求出某区间每一个数的和。输入格式第一行包含两个整数 n,m分别表示该数列数字的个数和操作的总个数。第二行包含 n 个用空格分隔的整数 ai​其中第 i 个数字表示数列第 i 项的初始值。接下来 m 行每行包含 3 或 4 个整数表示一个操作具体如下1 x y k将区间 [x,y] 内每个数加上 k。2 x y输出区间 [x,y] 内每个数的和。输出格式输出包含若干行整数即为所有操作 2 的结果。输入输出样例输入5 5 1 5 4 2 3 2 2 4 1 2 3 2 2 3 4 1 1 5 1 2 1 4输出11 8 20说明/提示对于 15% 的数据n≤8m≤10。对于 35% 的数据n≤103m≤104。对于 100% 的数据1≤n,m≤105ai​,k 为正数且任意时刻数列的和不超过 2×1018。题解#includebits/stdc.h using namespace std; using lllong long; //大根树 class SegmentTree { int n; vectorlltree; vectorlllazy; void maintain(int o) { tree[o] tree[o*2]tree[o*21]; } //构建线段树 void build(const vectorlla,int o, int l, int r) { if (lr) { tree[o]a[l]; return; } int m(lr)/2; build(a,o*2,l,m); build(a,o*21,m1,r); maintain(o); } //懒标记下发 void push(int o,int l,int r) { if (lazy[o]!0) { int m (l r) / 2; // 更新左儿子 tree[o*2] lazy[o] * (m - l 1); lazy[o*2] lazy[o]; // 更新右儿子 tree[o*21] lazy[o] * (r - m); lazy[o*21] lazy[o]; lazy[o]0; } } //区域更新 void update(int o,int l,int r,int ql,int qr,ll val) { if (qlr||lqr) { return ; } if (qllrqr) { tree[o] val * (r - l 1); lazy[o] val; return; } int m(lr)/2; push(o, l, r); update(o*2,l,m,ql,qr,val); update(o*21,m1,r,ql,qr,val); maintain(o); } ll query(int o,int l,int r,int ql,int qr) { // if (qlr||lqr) { // return 0; // } if (qllrqr) { return tree[o]; } push(o,l,r); int m(lr)/2; ll l_res 0, r_res 0; if (qlm) { l_resquery(o*2,l,m,ql,qr); } if (qrm) { r_resquery(o*21,m1,r,ql,qr); } return l_resr_res; } public: SegmentTree(const vectorlla) :n(a.size()),tree(4*n),lazy(4*n) { build(a,1,0,n-1); } void update(int l,int r,ll val) { update(1,0,n-1,l,r,val); } ll query(int ql,int qr) { return query(1,0,n-1,ql,qr); } }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n,m; cinnm; vectorlla(n); for (int i0;in;i) cina[i]; SegmentTree t(a); while(m--){ int p; cinp; if (p1) { ll x,y,k; cinxyk; t.update(x-1,y-1,k); }else { ll x,y; cinxy; coutt.query(x-1,y-1)\n; } } return 0; }接下来让我们一起分析分析这段代码解释在代码注释里。先简要介绍大体结构#includebits/stdc.h//万能头 using namespace std; using lllong long;//简化代码 //定义了一个线段树的类 class SegmentTree { int n;//树的大小 vectorlltree;//核心数组也是二叉树通过下标的关系来连接 //如 1 是 2 和 3 的根 // 2 是 4 和 5 的根 //也就是 i 是 i*2 和 i*21 的根 vectorlllazy;//懒标记作用是让每一次的更新数组都停留在中间的某个节点 //也就是需要更新的区域的根节点可能不止一个上只有当你要查询的时候碰到了就把标记往下传。 //此处使用两个数组之间是通过下标一一对应当题目复杂懒标记种类多也可以使用结构体 public: }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr);//加速 return 0; }再解释函数部分//维护函数用来维护线段树 void maintain(int o) { tree[o] tree[o*2]tree[o*21]; //此处加法是因为题目是求和可根据题意修改逻辑 }//构建线段树 void build(const vectorlla,int o, int l, int r) { //a数组为题目所给o是当前根节点l和r是当前根节点所包含的a数组区域值在0到n-1; if (lr) {//到叶子节点了 tree[o]a[l]; return; } int m(lr)/2; //如果lr超限可以用 r(l-r)/2;更保险 build(a,o*2,l,m);//建立左子树 build(a,o*21,m1,r);//建立右子树 maintain(o);//递归回去时要不断维护线段树就像从下往上建金字塔一样 }//懒标记下发 void push(int o,int l,int r) { if (lazy[o]!0) {//如果等于0就以为着该节点没有未处理的懒标记 int m (l r) / 2; // 更新左子树 tree[o*2] lazy[o] * (m - l 1); //乘以(m - l 1) 是因为这个节点包含了(m - l 1)个数结合当前逻辑每个数都要增加如果汇聚到根就要乘这么多。 lazy[o*2] lazy[o]; //懒标记继续下传 //可优化的点对于叶子节点的懒标记不可能进行下发基于这一点可以节省空间 // 更新右子树 tree[o*21] lazy[o] * (r - m); lazy[o*21] lazy[o]; lazy[o]0;//消除懒标记 } }//区域更新 void update(int o,int l,int r,int ql,int qr,ll val) { //l和r是当前区域ql和qr是需要更新的区域val是更新值 if (qlr||lqr) { return ; }//如果 当前区域 和 目标区域 没有交集就直接返回 if (qllrqr) {//如果 当前区域 完全在 目标区域 内就进行更新和懒标记添加 tree[o] val * (r - l 1); lazy[o] val; return; } int m(lr)/2; push(o, l, r);//下发懒标记再继续更新 update(o*2,l,m,ql,qr,val); update(o*21,m1,r,ql,qr,val); maintain(o);//维护 }//区域查询 ll query(int o,int l,int r,int ql,int qr) { // if (qlr||lqr) { // return 0; // } //此处的区间交集判断可有可无因为最后面两个if判断已经保证了没有交集的部分不会进行递归 if (qllrqr) { return tree[o]; } push(o,l,r); int m(lr)/2; ll l_res 0, r_res 0; if (qlm) {//如果是 就代表查询区间完全在右子树另一个同理 l_resquery(o*2,l,m,ql,qr); } if (qrm) { r_resquery(o*21,m1,r,ql,qr); } return l_resr_res;//返回区间的和 }public: //构造函数 //初始化列表顺序不可变优点是无额外开销涉及C内部 SegmentTree(const vectorlla) :n(a.size()),tree(4*n10),lazy(4*n10) { build(a,1,0,n-1); } //以下函数重复是为了简化后面使用时的书写。 void update(int l,int r,ll val) { update(1,0,n-1,l,r,val); } ll query(int ql,int qr) { return query(1,0,n-1,ql,qr); }类的部分解释结束。int n,m; cinnm; vectorlla(n); for (int i0;in;i) cina[i]; SegmentTree t(a);//定义一个线段树的类 while(m--){ int p; cinp; if (p1) { ll x,y,k; cinxyk; t.update(x-1,y-1,k);//减一是因为要契合数组下标是从0开始的 }else { ll x,y; cinxy; coutt.query(x-1,y-1)\n; } } return 0;当当当当大功告成不枉我又学了一天的线段树。如果还有不解或写错的地方欢迎在评论区留言小萤还会继续更新算法。