线段树简单 *** 作模板复习(本来就不熟练)

概述// 参考博客 https://www.cnblogs.com/TheRoadToTheGold/p/6254255.html#4175712 // 懒人标记： 表示当前结点区间值已经改变，但是下面的区间还没改变。每次询问到有懒人标记的结点时，在进一步询问他的子节点时，下放标记(下放的同时改变了子结点的值，并且赋予子节点懒人标记) // 因此 当将要查询对应区间时候 之前修改区间的 *** 作在此时才进行

// 参考博客 https://www.cnblogs.com/TheRoadToTheGold/p/6254255.html#4175712

// 懒人标记： 表示当前结点区间值已经改变，但是下面的区间还没改变。每次询问到有懒人标记的结点时，在进一步询问他的子节点时，下放标记(下放的同时改变了子结点的值，并且赋予子节点懒人标记)
// 因此 当将要查询对应区间时候 之前修改区间的 *** 作在此时才进行 -- 因此叫懒人标记 
 1 #include<cstdio>  2 using namespace std;  3   4 const int MAXN = 100000;  5   6 int ans;// 每次查询的结果  7 struct node {  8     int l,r,w,f;// 左端点下标,右端点下标，l~r各点权值和,"懒人"标记(在修改区间值时候，‘手动‘修改懒人标记)  9 }tree[4*MAXN+1]; 10  11 inline voID build(int k,int ll,int rr) {// 建树 12     tree[k].l = ll,tree[k].r = rr; 13     if(tree[k].l == tree[k].r) { 14         scanf("%d",&tree[k].w); 15         return ; 16     } 17     int m = (ll + rr) / 2; 18     build(k*2,ll,m); 19     build(k*2+1,m+1,rr); 20     tree[k].w = tree[k*2].w + tree[k*2+1].w; 21 } 22  23 inline voID down(int k) {// "懒"标记下传 24     tree[k*2].f += tree[k].f; 25     tree[k*2+1].f += tree[k].f; 26     tree[k*2].w += tree[k].f * (tree[k*2].r - tree[k*2].l + 1); 27     tree[k*2+1].w += tree[k].f * (tree[k*2+1].r - tree[k*2+1].l + 1); 28     tree[k].f = 0;// 表明下传过了 不能重复下传(下次查询到此不再下传) 29 } 30  31 inline voID query_point(int k,int x) {// 单点查询(第x位置) 32     if(tree[k].l == tree[k].r) { 33         ans = tree[k].w; 34         return ; 35     } 36     if(tree[k].f) down(k); 37     int m = (tree[k].l + tree[k].r) / 2; 38     if(x <= m) query_point(k*2,x); 39     else query_point(k*2+1,x); 40 } 41  42 inline voID change_point(int k,int x,int v) {// 单点修改 x->x+v 43     if(tree[k].l == tree[k].r) { 44         tree[k].w += v; 45         return ; 46     } 47     if(tree[k].f) down(k); 48     int m = (tree[k].l + tree[k].r) / 2; 49     if(x <= m) change_point(k*2,x,v); 50     else change_point(k*2+1,v); 51     tree[k].w = tree[k*2].w + tree[k*2+1].w; 52 } 53  54 inline voID query_interval(int k,int y) {// 区间查询 x~y之和 55     if(tree[k].l >= x && tree[k].r <= y) { 56         ans += tree[k].w; 57         return ; 58     } 59     if(tree[k].f) down(k); 60     int m = (tree[k].l + tree[k].r) / 2; 61     if(x <= m) query_interval(k*2,y); 62     if(y > m) query_interval(k*2+1,y); 63 } 64  65 inline voID change_interval(int k,int y,int v) {// 区间修改  x~y每个点+v 66     if(tree[k].l >= x && tree[k].r <= y) { 67         tree[k].w += (tree[k].r - tree[k].l + 1) * v;// 改变区间值 68         tree[k].f += v;// 懒人标记 69         return ; 70     } 71     if(tree[k].f) down(k); 72     int m = (tree[k].l + tree[k].r) / 2; 73     if(x <= m) change_interval(k*2,y,v); 74     if(y > m) change_interval(k*2+1,v); 75     tree[k].w += tree[k*2].w + tree[k*2+1].w; 76 } 77  78 int main() { 79     int n,m; 80     scanf("%d",&n); 81     build(1,1,n); 82     scanf("%d",&m); 83     int p; 84     int x,v; 85     for(int i = 0; i != m; ++i) { 86         scanf("%d",&p); 87         ans = 0; 88         if(p == 1) { 89             scanf("%d",&x); 90             query_point(1,x);// 单点查询 输出第k个数 91             printf("%d\n",ans); 92         } 93         else if(p == 2) { 94             scanf("%d%d",&x,&v); 95             change_point(1,v);// 单点修改 x->x+v 96         } 97         else if(p == 3) { 98             scanf("%d%d",&y); 99             query_interval(1,y);// 区间查询 x~y之和100             printf("%d\n",ans);101         }102         else {103             scanf("%d%d%d",&y,&v);104             change_interval(1,v);// 区间修改 x~y每个点+v105         }106     }107     return 0;108 }

总结

以上是内存溢出为你收集整理的线段树简单 *** 作模板复习(本来就不熟练)全部内容，希望文章能够帮你解决线段树简单 *** 作模板复习(本来就不熟练)所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。