acwing 243. 一个简单的整数问题2 树状数组 线段树
地址 https://www.acwing.com/problem/content/description/244/
给定一个长度为N的数列A，以及M条指令，每条指令可能是以下两种之一：
1、“C l r d”，表示把 A[l],A[l+1],…,A[r] 都加上 d。
2、“Q l r”，表示询问 数列中第 l~r 个数的和。
对于每个询问，输出一个整数表示答案。
输入格式
第一行两个整数N,M。
第二行N个整数A[i]。
接下来M行表示M条指令，每条指令的格式如题目描述所示。
输出格式
对于每个询问，输出一个整数表示答案。
每个答案占一行。
数据范围 1≤N,M≤105, |d|≤10000, |A[i]|≤1000000000 输入样例： 10 5 1 2 3 4 5 6 7 8 9 10 Q 4 4 Q 1 10 Q 2 4 C 3 6 3 Q 2 4 输出样例： 4 55 9 15
解答
线段树模板 与上一题几乎一摸一样的板子 可以解决
可以说线段树就是解决此类问题的方案 缺点是相对树状数组 代码稍多
1 #include <iostream> 2 #include <algorithm> 3 #include <string> 4 5 using namespace std; 6 7 8 const int maxn = 1e5 + 6; 9 int n; 10 int a[maxn]; 11 int q; 12 13 struct node { 14 int l, r; 15 long long sum, lazy; 16 void update(long long x) { 17 sum += 1ll * (r - l + 1)*x; 18 lazy += x; 19 } 20 }tree[maxn*4]; 21 22 void push_up(int x) { 23 tree[x].sum = tree[x << 1].sum + tree[x << 1 | 1].sum; 24 } 25 26 void push_down(int x) 27 { 28 int lazyval = tree[x].lazy; 29 if (lazyval) { 30 tree[x << 1].update(lazyval); 31 tree[x << 1 | 1].update(lazyval); 32 tree[x].lazy = 0; 33 } 34 35 } 36 37 void build(int x, int l, int r) { 38 tree[x].l = l; tree[x].r = r; 39 tree[x].sum = tree[x].lazy = 0; 40 if (l == r) { 41 tree[x].sum = a[l]; 42 } 43 else { 44 int mid = (l + r) / 2; 45 build(x << 1, l, mid); 46 build(x << 1 | 1, mid + 1, r); 47 push_up(x); 48 } 49 } 50 51 void update(int x, int l, int r, long long val) 52 { 53 int L = tree[x].l, R = tree[x].r; 54 if (l <= L && R <= r) { 55 tree[x].update(val); 56 } 57 else { 58 push_down(x); 59 int mid = (L + R) / 2; 60 if (mid >= l) update(x << 1, l, r, val); 61 if (r > mid) update(x << 1 | 1, l, r, val); 62 push_up(x); 63 } 64 } 65 66 long long query(int x, int l, int r) 67 { 68 int L = tree[x].l, R = tree[x].r; 69 if (l <= L && R <= r) { 70 return tree[x].sum; 71 } 72 else { 73 push_down(x); 74 long long ans = 0; 75 int mid = (L + R) / 2; 76 if (mid >= l) ans += query(x << 1, l, r); 77 if (r > mid) ans += query(x << 1 | 1, l, r); 78 push_up(x); 79 return ans; 80 } 81 } 82 83 84 85 86 int main() 87 { 88 cin >> n >> q; 89 for (int i = 1; i <= n; i++) { 90 cin >> a[i]; 91 } 92 build(1, 1, n); 93 94 for (int i = 1; i <= q; i++) { 95 string s; 96 int l, r, d, q; 97 cin >> s; 98 if (s == "Q") { 99 cin >> l>>r; 100 cout << query(1, l, r) << endl; 101 } 102 else { 103 cin >> l >> r >> d; 104 update(1, l, r, d); 105 } 106 } 107 108 return 0; 109 }