線段樹（結構體）模板

#include<iostream> #include<cstdio> #include<queue> #include<cstring> #include<algorithm> #include<map> #include<cmath> #include<string> using namespace std; typedef long long ll; int ans; struct node {int l, r, w;int f; }; struct node tree[50000 * 4 + 1]; void BuildSegmentTree(int k, int l, int r) // 建線段樹 {tree[k].l = l;tree[k].r = r;if(l == r){scanf("%lld", &tree[k].w);return ;}int m = (tree[k].l + tree[k].r) >> 1;BuildSegmentTree(k << 1, l, m);BuildSegmentTree(k << 1 | 1, m + 1, r);tree[k].w = tree[k << 1].w + tree[k << 1 | 1].w; } void down(int k) // 懶標記 {tree[k << 1].f += tree[k].f;tree[k << 1 | 1].f += tree[k].f;tree[k << 1]. w += tree[k].f * (tree[k << 1].r - tree[k <<1].l + 1);tree[k << 1 |1].w += tree[k].f * (tree[k << 1| 1].r - tree[k << 1| 1].l + 1);tree[k].f = 0; } void Single_Point_Modification(int k, int x, int y) // 單點修改 {if(tree[k].l == tree[k].r){tree[k].w += y;return ;}int m = (tree[k].l + tree[k].r) >> 1;if(x <= m) Single_Point_Modification(k << 1,x, y);else Single_Point_Modification(k << 1 | 1, x, y);tree[k].w = tree[k << 1].w + tree[k << 1 | 1]. w; } void Single_Point_Query(int k, int x) // 單點查詢 {if(tree[k].l == tree[k].r){ans = tree[k].w;return ;}if(tree[k].f) down(k);int m = (tree[k].l + tree[k].r) >> 1;if(x <= m) Single_Point_Query(k << 1, x);else Single_Point_Query(k << 1 | 1, x); } void Interval_modification(int k, int x, int y,int z) //區間修改 {if(tree[k].l >= x && tree[k].r <= y){tree[k].w += (tree[k].r - tree[k].l + 1) * z;tree[k].f += z;return;}if(tree[k].f) down(k);int m = (tree[k].l + tree[k].r) >> 1;if(x <= m) Interval_modification(k << 1, x, y, z);if(y > m) Interval_modification(k << 1 | 1, x, y, z);tree[k].w = tree[k << 1].w + tree[k << 1 | 1].w; } void Interval_Query(int k, int x, int y) //區間查詢 {if(tree[k].l >= x && tree[k].r <= y){ans += tree[k].w;return ;}if(tree[k].f) down(k);int m = (tree[k].l + tree[k].r) / 2;if(x <= m) Interval_Query(k << 1, x, y);if(y > m) Interval_Query(k << 1 | 1, x, y); }char s[10]; int main() {int T, n;while(~scanf("%d",&T)){int cas = 0;while(T--){scanf("%d", &n);BuildSegmentTree(1,1,n);printf("Case %d:\n",++ cas);while(1){int x, y, z;getchar();scanf("%s",s);if(s[0] == 'E')break;else if(s[0]== 'A') // 區間修改{scanf("%d %d %d", &x, &y, &z);Interval_modification(1,x,y,z);}else if(s[0] =='B') // 區間查詢{ans = 0;scanf("%d %d", &x, &y);Interval_Query(1, x, y);printf("%d\n",ans);}else if(s[0]=='C') // 單點修改{scanf("%d %d", &x, &y);Single_Point_Modification(1,x,y);}else if(s[0]=='D') // 單點查詢{ans = 0;scanf("%d", &x);Single_Point_Query(1,x);printf("%d\n",ans);}}}}return 0; }

?

轉載于:https://www.cnblogs.com/lcchy/p/10139640.html

總結

以上是生活随笔為你收集整理的线段树（结构体建法_QAQ）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。