思路1：
线段树区间更新。
实现：
1 #include <cstdio> 2 #include <cstring> 3 using namespace std; 4 typedef long long ll; 5 const int N = 100005; 6 ll tree[N * 4], lazy[N * 4], a[N]; 7 int n, m; 8 9 void build(int num, int l, int r) 10 { 11 if (l == r) { tree[num] = a[l]; return; } 12 int m = l + r >> 1; 13 build(num * 2, l, m); 14 build(num * 2 + 1, m + 1, r); 15 tree[num] = tree[num * 2] + tree[num * 2 + 1]; 16 } 17 18 void pushdown(int num, int cl, int cr) 19 { 20 if (!lazy[num]) return; 21 tree[num * 2] += lazy[num] * cl; 22 tree[num * 2 + 1] += lazy[num] * cr; 23 lazy[num * 2] += lazy[num]; 24 lazy[num * 2 + 1] += lazy[num]; 25 lazy[num] = 0; 26 } 27 28 void update(int num, int l, int r, int x, int y, ll dx) 29 { 30 if (x <= l && y >= r) { tree[num] += (r - l + 1) * dx; lazy[num] += dx; return; } 31 int m = l + r >> 1; 32 pushdown(num, m - l + 1, r - m); 33 if (x <= m) update(num * 2, l, m, x, y, dx); 34 if (y >= m + 1) update(num * 2 + 1, m + 1, r, x, y, dx); 35 tree[num] = tree[num * 2] + tree[num * 2 + 1]; 36 } 37 38 ll query(int num, int l, int r, int x, int y) 39 { 40 if (x <= l && y >= r) return tree[num]; 41 int m = l + r >> 1; 42 pushdown(num, m - l + 1, r - m); 43 ll ans = 0; 44 if (x <= m) ans += query(num * 2, l, m, x, y); 45 if (y >= m + 1) ans += query(num * 2 + 1, m + 1, r, x, y); 46 return ans; 47 } 48 49 int main() 50 { 51 scanf("%d %d", &n, &m); 52 for (int i = 1; i <= n; i++) scanf("%lld", &a[i]); 53 getchar(); 54 build(1, 1, n); 55 char tmp; int x, y; ll d; 56 for (int i = 0; i < m; i++) 57 { 58 scanf("%c", &tmp); 59 if (tmp == 'Q') { scanf("%d %d", &x, &y); getchar(); printf("%lld ", query(1, 1, n, x, y)); } 60 else { scanf("%d %d %lld", &x, &y, &d); getchar(); update(1, 1, n, x, y, d); } 61 } 62 return 0; 63 }
思路2：
树状数组区间更新+区间查询。
http://blog.csdn.net/fsahfgsadhsakndas/article/details/52650026
实现：
1 #include <cstdio> 2 using namespace std; 3 typedef long long ll; 4 const int MAXN = 100005; 5 ll bit0[MAXN], bit1[MAXN]; 6 int n, m; 7 8 int lowbit(int x) { return x & -x; } 9 10 void add(ll * bit, int i, ll x) 11 { 12 while (i <= n) { bit[i] += x; i += lowbit(i); } 13 } 14 15 ll sum(ll * bit, int i) 16 { 17 ll ans = 0; 18 while (i) { ans += bit[i]; i -= lowbit(i); } 19 return ans; 20 } 21 22 ll query(int x) 23 { 24 return x * sum(bit0, x) - sum(bit1, x); 25 } 26 27 int main() 28 { 29 scanf("%d %d", &n, &m); 30 char tmp; int x, y; ll d; 31 for (int i = 1; i <= n; i++) 32 { 33 scanf("%lld", &d); 34 add(bit0, i, d); 35 add(bit0, i + 1, -d); 36 add(bit1, i, (i - 1) * d); 37 add(bit1, i + 1, -i * d); 38 } 39 getchar(); 40 for (int i = 0; i < m; i++) 41 { 42 scanf("%c", &tmp); 43 if (tmp == 'Q') 44 { 45 scanf("%d %d", &x, &y); getchar(); 46 ll r = query(y), l = query(x - 1); 47 printf("%lld ", r - l); 48 } 49 else 50 { 51 scanf("%d %d %lld", &x, &y, &d); getchar(); 52 add(bit0, x, d); 53 add(bit0, y + 1, -d); 54 add(bit1, x, (x - 1) * d); 55 add(bit1, y + 1, -y * d); 56 } 57 } 58 return 0; 59 }
bit1的作用就是快速（O(logN)）计算((j - 1) * c[j])(1 <= j <= i)的和。甚至换成单点更新的线段树也是行得通的。
1 #include <cstdio> 2 #include <iostream> 3 using namespace std; 4 typedef long long ll; 5 const int MAXN = 100005; 6 ll bit[MAXN], tree[MAXN * 4]; 7 int n, m; 8 9 int lowbit(int x) { return x & -x; } 10 11 void add(int i, ll x) 12 { 13 while (i <= n) { bit[i] += x; i += lowbit(i); } 14 } 15 16 ll sum(int i) 17 { 18 ll ans = 0; 19 while (i) { ans += bit[i]; i -= lowbit(i); } 20 return ans; 21 } 22 23 void update(int num, int l, int r, int x, ll dx) 24 { 25 if (l == r) { tree[num] += dx; return; } 26 int m = l + r >> 1; 27 if (x <= m) update(num * 2, l, m, x, dx); 28 else update(num * 2 + 1, m + 1, r, x, dx); 29 tree[num] = tree[num * 2] + tree[num * 2 + 1]; 30 } 31 32 ll query(int num, int l, int r, int x, int y) 33 { 34 if (x <= l && y >= r) return tree[num]; 35 int m = l + r >> 1; 36 ll ans = 0; 37 if (x <= m) ans += query(num * 2, l, m, x, y); 38 if (y >= m + 1) ans += query(num * 2 + 1, m + 1, r, x, y); 39 return ans; 40 } 41 42 ll get_ans(int x) 43 { 44 if (x < 1) return 0; 45 return x * sum(x) - query(1, 1, n + 1, 1, x); 46 } 47 48 int main() 49 { 50 scanf("%d %d", &n, &m); 51 char tmp; int x, y; ll d; 52 for (int i = 1; i <= n; i++) 53 { 54 scanf("%lld", &d); 55 add(i, d); add(i + 1, -d); 56 update(1, 1, n + 1, i, (i - 1) * d); 57 update(1, 1, n + 1, i + 1, -i * d); 58 } 59 getchar(); 60 for (int i = 0; i < m; i++) 61 { 62 scanf("%c", &tmp); 63 if (tmp == 'Q') 64 { 65 scanf("%d %d", &x, &y); getchar(); 66 ll r = get_ans(y); 67 ll l = get_ans(x - 1); 68 printf("%lld ", r - l); 69 } 70 else 71 { 72 scanf("%d %d %lld", &x, &y, &d); getchar(); 73 add(x, d); 74 add(y + 1, -d); 75 update(1, 1, n + 1, x, ((ll)x - 1) * d); 76 update(1, 1, n + 1, y + 1, -(ll)y * d); 77 } 78 } 79 return 0; 80 }