本文共 2456 字，大约阅读时间需要 8 分钟。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 using namespace std; 12 typedef long long LL; 13 const LL MaxN = 1e5; 14 typedef struct{ 15 int l, r; 16 LL sum, lazy; 17 void update(LL C) 18 { 19 sum += 1LL*(r-l+1)*C; 20 lazy += C; 21 } 22 } Power; 23 Power segtree[MaxN<<2]; 24 int n, q; 25 int num[MaxN+5]; 26 27 void push_up(int x) 28 { 29 segtree[x].sum = segtree[x<<1].sum + segtree[x<<1|1].sum; 30 } 31 void push_down(int x) 32 { 33 int lazyval = segtree[x].lazy; 34 if(lazyval){ 35 segtree[x<<1].update(lazyval); 36 segtree[x<<1|1].update(lazyval); 37 segtree[x].lazy = 0; 38 } 39 } 40 41 //建树 42 void Build(int x, int l, int r) 43 { 44 segtree[x].l = l, segtree[x].r = r; 45 segtree[x].sum = segtree[x].lazy = 0; 46 if(l == r){ 47 segtree[x].sum = num[l]; 48 return; 49 } 50 int mid = (l + r)/2; 51 Build(x<<1, l, mid); 52 Build(x<<1|1, mid+1, r); 53 push_up(x); 54 } 55 56 //点修改，假设num[i]+C 57 void Update_point(int x, int i, int C) 58 { 59 int l = segtree[x].l, r = segtree[x].r; 60 if(l == r){ 61 segtree[x].sum += C; 62 return; 63 } 64 int mid = (l+r)/2; 65 if(i <= mid) Update_point(x<<1, i, C); 66 else Update_point(x<<1|1, i, C); 67 push_up(x); 68 } 69 70 //区间修改，假设num[L, R] += C 71 void Update_segment(int x, int L, int R, LL C) 72 { 73 int l = segtree[x].l, r = segtree[x].r; 74 if(l >= L && r <= R){ 75 segtree[x].update(C); 76 } 77 else{ 78 push_down(x); 79 int mid = (l + r)/2; 80 if(mid >= L) Update_segment(x<<1, L, R, C); 81 if(mid < R) Update_segment(x<<1|1, L, R, C); 82 push_up(x); 83 } 84 } 85 86 //区间查询，假设查询num[L, R]; 87 LL Query_segment(int x, int L, int R) 88 { 89 int l = segtree[x].l, r = segtree[x].r; 90 if(l >= L && r <= R){ 91 return segtree[x].sum; 92 } 93 else{ 94 push_down(x); 95 LL ans = 0; 96 int mid = (l + r)/2; 97 if(mid >= L) ans += Query_segment(x<<1, L, R); 98 if(mid < R) ans += Query_segment(x<<1|1, L, R); 99 push_up(x);100 return ans;101 }102 }103 104 int main()105 {106 cin >> n;107 for(int i = 1;i <= n;i++){108 scanf("%d", num + i);109 }110 Build(1, 1, n);111 scanf("%d", &q);112 for(int i = 1;i <= q;i++){113 int l, r, C;114 scanf("%d %d %d", &l, &r, &C);115 Update_segment(1, l, r, C);116 printf("%lld\n", Query_segment(1, l, r));117 }118 return 0;119 }
转载于:https://www.cnblogs.com/ScaleCX/p/9400582.html