线段是算法比赛常用于一个数组各个区间的特定值以及更新特定区间的值。可以看下面的图来了解线段树是如何存储的可以看到线段树是一颗二叉树其中每个叶子节点都是单独一个数这里线段树的存储方式采用的是线性数组模拟二叉树同时采用的是分治法既然我要求某个区间的和那我可以去求左边的和加上右边的和这样递归下去构建class segment_tree{ public: segment_tree(vectorint arr){ int narr.size(); node.resize(4*n,0); lazy.resize(4*n,0); sizen; build(0,n-1,0,arr);//构建一棵树 } private: vectorint node; vectorint lazy; int size; void build(int l,int r,int treenode,vectorint arr){ if(lr){ node[treenode]arr[l]; return ; } //到达了叶子节点 //采用分治法的思想 int lctreenode*21; int rctreenode*22; int mid(lr)/2; build(l,mid,lc,arr); build(mid1,r,rc,arr); node[treenode]node[lc]node[rc]; } };同过调用构造函数和build函数递归构造这颗线段树接下来来看更新函数void updata(int l,int r,int val,int start,int end,int treenode){ if(rstart||lend){ return ; }//构建的区间完全不在当前这个小线段树上 if(lstartrend){ node[treenode]val*(end-start1); lazy[treenode]val;//懒标记节省了大量时间 return ; }//当前线段树完全在要更新的范围内 push_down(treenode,start,end);//注意要先把当前线段树的懒标记传下去 //要不然直接递归会丢掉以前更新的东西 int lctreenode*21; int rctreenode*22; int mid(startend)/2; updata(l,r,val,start,mid,lc); updata(l,r,val,mid1,end,rc); //更新完左右节点当前节点也要更新 node[treenode]node[lc]node[rc]; return ; }接下来来看询问操作int query(int l,int r,int start,int end,int treenode){ if(rstart||lend){ return 0; }//询问的区间完全不在当前这个小线段树上 if(lstartrend){ return node[treenode]; }//当前线段树完全在询问范围内 push_down(treenode,start,end);//注意要先把当前线段树的懒标记传下去 //要不然直接递归会丢掉以前更新的东西 int lctreenode*21; int rctreenode*22; int mid(startend)/2; int l_sumquery(l,r,start,mid,lc); int r_sumquery(l,r,mid1,end,rc); //询问完左右区间节点当前节点给答案 int suml_sumr_sum; return sum; }这里都用到了push_down函数void push_down(int treenode,int start,int end){ int lctreenode*21; int rctreenode*22; int mid(startend)/2; node[lc]lazy[treenode]*(mid-start1); node[rc]lazy[treenode]*(end-mid); lazy[lc]lazy[treenode]; lazy[rc]lazy[treenode]; //向下传递懒标记 lazy[treenode]0; }注意线段树可能数值很大因此有的题目需要取余操作或者说是int 改longlong接下来看例题P3372 【模板】线段树 1 - 洛谷这道题目就是个模版题直接编写一下主函数用线段树模版就能通过上述题目只有一种更新操作接下来看多种更新操作的情况P3373 【模板】线段树 2 - 洛谷这道题目懒标记就要用两个了还有个问题就是当push_down是先清除乘法标记还是先清除加法标记因此我们定义个顺序当更新乘法操作时先将该点存的加法标记也乘上kpush_down先乘后加的顺序操作。即对一个区间执行先加后乘的操作时乘法时更新加法标记先乘后加是不影响的可以看做先加0再乘法再加法再乘1对于push_down函数void push_down(int start, int end, int treenode) { int mid (start end) / 2; int lc treenode * 2 1; // 左儿子 int rc treenode * 2 2; // 右儿子 // 1. 先处理乘法下放 // 儿子的值乘父亲的乘法标记 node[lc] (node[lc] * lazy1[treenode]) % m; node[rc] (node[rc] * lazy1[treenode]) % m; // 儿子的乘法标记乘父亲的乘法标记 lazy1[lc] (lazy1[lc] * lazy1[treenode]) % m; lazy1[rc] (lazy1[rc] * lazy1[treenode]) % m; // 【关键】儿子的加法标记也要乘父亲的乘法标记 lazy[lc] (lazy[lc] * lazy1[treenode]) % m; lazy[rc] (lazy[rc] * lazy1[treenode]) % m; // 2. 再处理加法下放 // 儿子的值加父亲的加法标记 node[lc] (node[lc] lazy[treenode] * (mid - start 1)) % m; node[rc] (node[rc] lazy[treenode] * (end - mid)) % m; // 儿子的加法标记加父亲的加法标记 lazy[lc] (lazy[lc] lazy[treenode]) % m; lazy[rc] (lazy[rc] lazy[treenode]) % m; // 3. 清空父亲的标记 lazy1[treenode] 1; lazy[treenode] 0; } };#includeiostream #includevector #define int long long using namespace std; int m; class segment_tree { public: segment_tree(vectorint arr) { int n arr.size(); size n; lazy.resize(4 * n, 0); node.resize(4 * n, 0); lazy1.resize(4 * n, 1); build(arr, 0, 0, n - 1); } int query(int l, int r) { return query(l, r, 0, size - 1, 0); } void updata(int l, int r, int val, int op) { if (op 2) updata(l, r, val, 0, size - 1, 0); else updata1(l, r, val, 0, size - 1, 0); } private: vectorint lazy; vectorint node; vectorint lazy1; int size; void build(vectorint arr, int treenode, int l, int r) { if (l r) { node[treenode] arr[l] % m; return; } int mid (l r) / 2; int leftchild treenode * 2 1; int rightchild treenode * 2 2; build(arr, leftchild, l, mid); build(arr, rightchild, mid 1, r); node[treenode] (node[leftchild] node[rightchild]) % m; } int query(int l, int r, int start, int end, int treenode) { if (r start || l end) { return 0; } if (r end l start) { return node[treenode]; } int mid (start end) / 2; push_down(start, end, treenode); int left_sum query(l, r, start, mid, treenode * 2 1); int right_sum query(l, r, mid 1, end, treenode * 2 2); int sum left_sum right_sum; return sum % m; } void updata(int l, int r, int val, int start, int end, int treenode) { if (r start || l end) { return; } if (r end l start) { node[treenode] (end - start 1) * val; node[treenode] % m; lazy[treenode] val; lazy[treenode] % m; return; } int mid (start end) / 2; push_down(start, end, treenode); updata(l, r, val, start, mid, treenode * 2 1); updata(l, r, val, mid 1, end, treenode * 2 2); node[treenode] (node[treenode * 2 1] node[treenode * 2 2]) % m; } void updata1(int l, int r, int val, int start, int end, int treenode) { if (r start || l end) { return; } if (r end l start) { node[treenode] * val; node[treenode] % m; lazy1[treenode] * val; lazy1[treenode] % m; lazy[treenode] * val; lazy[treenode] % m; return; } int mid (start end) / 2; push_down(start, end, treenode); updata1(l, r, val, start, mid, treenode * 2 1); updata1(l, r, val, mid 1, end, treenode * 2 2); node[treenode] (node[treenode * 2 1] node[treenode * 2 2]) % m; } // 重点看这里帮你整理得干干净净 void push_down(int start, int end, int treenode) { int mid (start end) / 2; int lc treenode * 2 1; // 左儿子 int rc treenode * 2 2; // 右儿子 // 1. 先处理乘法下放 // 儿子的值乘父亲的乘法标记 node[lc] (node[lc] * lazy1[treenode]) % m; node[rc] (node[rc] * lazy1[treenode]) % m; // 儿子的乘法标记乘父亲的乘法标记 lazy1[lc] (lazy1[lc] * lazy1[treenode]) % m; lazy1[rc] (lazy1[rc] * lazy1[treenode]) % m; // 【关键】儿子的加法标记也要乘父亲的乘法标记 lazy[lc] (lazy[lc] * lazy1[treenode]) % m; lazy[rc] (lazy[rc] * lazy1[treenode]) % m; // 2. 再处理加法下放 // 儿子的值加父亲的加法标记 node[lc] (node[lc] lazy[treenode] * (mid - start 1)) % m; node[rc] (node[rc] lazy[treenode] * (end - mid)) % m; // 儿子的加法标记加父亲的加法标记 lazy[lc] (lazy[lc] lazy[treenode]) % m; lazy[rc] (lazy[rc] lazy[treenode]) % m; // 3. 清空父亲的标记 lazy1[treenode] 1; lazy[treenode] 0; } }; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin n q m; vectorint arr(n); for (int i 0; i n; i) { cin arr[i]; } segment_tree tr(arr); while (q--) { int op; cin op; if (op 1) { int x, y, k; cin x y k; tr.updata(x - 1, y - 1, k, 1); } else if (op 2) { int x, y, k; cin x y k; tr.updata(x - 1, y - 1, k, 2); } else { int x, y; cin x y; cout tr.query(x - 1, y - 1) % m \n; } } return 0; }上述是两个更新操作如果再多一点更新操作呢Problem - 4578上一道题是在假设乘法再加法并解决当要先加后乘时的情况这题是三种情况可以说定优先级changemutadd即假设先更改再乘最后加的顺序更新当更新change时要同时改变以前出现的加法和乘法当出现乘法时要改变以前的加法。这里计算不同平方时是有技巧的void change(int l, int r, int val, int start, int end, int treenode) { if (r start || l end) return; if (l start r end) { int v val % MOD; int v2 (v * v) % MOD; int v3 (v2 * v) % MOD; int len end - start 1; nodep1[treenode] (v * len) % MOD; nodep2[treenode] (v2 * len) % MOD; nodep3[treenode] (v3 * len) % MOD; lazycha[treenode] v; lazyadd[treenode] 0; lazymut[treenode] 1; return; } push_down(treenode, start, end); int lc treenode * 2 1, rc treenode * 2 2, mid (start end) / 2; change(l, r, val, start, mid, lc); change(l, r, val, mid 1, end, rc); push_up(treenode); } void mut(int l, int r, int val, int start, int end, int treenode) { if (r start || l end) return; if (l start r end) { int v val % MOD; int v2 (v * v) % MOD; int v3 (v2 * v) % MOD; nodep1[treenode] (nodep1[treenode] * v) % MOD; nodep2[treenode] (nodep2[treenode] * v2) % MOD; nodep3[treenode] (nodep3[treenode] * v3) % MOD; lazyadd[treenode] (lazyadd[treenode] * v) % MOD; lazymut[treenode] (lazymut[treenode] * v) % MOD; return; } push_down(treenode, start, end); int lc treenode * 2 1, rc treenode * 2 2, mid (start end) / 2; mut(l, r, val, start, mid, lc); mut(l, r, val, mid 1, end, rc); push_up(treenode); } void add(int l, int r, int val, int start, int end, int treenode) { if (r start || l end) return; if (l start r end) { int v val % MOD; int v2 (v * v) % MOD; int v3 (v2 * v) % MOD; int len end - start 1; int p1 nodep1[treenode], p2 nodep2[treenode], p3 nodep3[treenode]; // 务必步步取模 nodep3[treenode] (p3 3 * v % MOD * p2 % MOD 3 * v2 % MOD * p1 % MOD v3 * len % MOD) % MOD; nodep2[treenode] (p2 2 * v % MOD * p1 % MOD v2 * len % MOD) % MOD; nodep1[treenode] (p1 v * len % MOD) % MOD; lazyadd[treenode] (lazyadd[treenode] v) % MOD; return; } push_down(treenode, start, end); int lc treenode * 2 1, rc treenode * 2 2, mid (start end) / 2; add(l, r, val, start, mid, lc); add(l, r, val, mid 1, end, rc); push_up(treenode); } void push_down(int treenode, int start, int end) { int lc treenode * 2 1; int rc treenode * 2 2; int mid (start end) / 2; int len_l mid - start 1; int len_r end - mid; if (lazycha[treenode] ! 0) { int v lazycha[treenode]; int v2 (v * v) % MOD; int v3 (v2 * v) % MOD; nodep1[lc] v * len_l % MOD; nodep2[lc] v2 * len_l % MOD; nodep3[lc] v3 * len_l % MOD; nodep1[rc] v * len_r % MOD; nodep2[rc] v2 * len_r % MOD; nodep3[rc] v3 * len_r % MOD; lazycha[lc] v; lazyadd[lc] 0; lazymut[lc] 1; lazycha[rc] v; lazyadd[rc] 0; lazymut[rc] 1; lazycha[treenode] 0; } if (lazymut[treenode] ! 1) { int v lazymut[treenode]; int v2 (v * v) % MOD; int v3 (v2 * v) % MOD; nodep1[lc] (nodep1[lc] * v) % MOD; nodep2[lc] (nodep2[lc] * v2) % MOD; nodep3[lc] (nodep3[lc] * v3) % MOD; lazyadd[lc] (lazyadd[lc] * v) % MOD; lazymut[lc] (lazymut[lc] * v) % MOD; nodep1[rc] (nodep1[rc] * v) % MOD; nodep2[rc] (nodep2[rc] * v2) % MOD; nodep3[rc] (nodep3[rc] * v3) % MOD; lazyadd[rc] (lazyadd[rc] * v) % MOD; lazymut[rc] (lazymut[rc] * v) % MOD; lazymut[treenode] 1; } if (lazyadd[treenode] ! 0) { int v lazyadd[treenode]; int v2 (v * v) % MOD; int v3 (v2 * v) % MOD; int p1 nodep1[lc], p2 nodep2[lc], p3 nodep3[lc]; nodep3[lc] (p3 3 * v % MOD * p2 % MOD 3 * v2 % MOD * p1 % MOD v3 * len_l % MOD) % MOD; nodep2[lc] (p2 2 * v % MOD * p1 % MOD v2 * len_l % MOD) % MOD; nodep1[lc] (p1 v * len_l % MOD) % MOD; lazyadd[lc] (lazyadd[lc] v) % MOD; p1 nodep1[rc], p2 nodep2[rc], p3 nodep3[rc]; nodep3[rc] (p3 3 * v % MOD * p2 % MOD 3 * v2 % MOD * p1 % MOD v3 * len_r % MOD) % MOD; nodep2[rc] (p2 2 * v % MOD * p1 % MOD v2 * len_r % MOD) % MOD; nodep1[rc] (p1 v * len_r % MOD) % MOD; lazyadd[rc] (lazyadd[rc] v) % MOD; lazyadd[treenode] 0; } }