题目链接：http://poj.org/problem?id=3468
参考：https://blog.csdn.net/qq_39562952/article/details/81298043
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #define mem(a,b) memset(a,b,sizeof(a)); 5 using namespace std; 6 typedef long long ll; 7 const int maxn = 500005; 8 const ll INF = 0x3f3f3f3f; 9 ll n,q,m; 10 ll a[maxn],b[maxn],c[maxn]; 11 ll lowbit(ll t) {//取出t的最低位１ 12 return t&(-t); 13 } 14 ll getsum(ll x) { 15 ll ans = 0; 16 for(int i = x; i > 0; i -= lowbit(i)) { 17 ans += x*b[i]-c[i]; 18 } 19 return ans; 20 } 21 void update(ll x,ll v) { 22 for(int i = x; i <= n; i+=lowbit(i)) { 23 b[i] += v; 24 c[i] += v*(x-1); 25 } 26 } 27 int main() 28 { 29 30 cin >> n >> q; 31 for(int i = 1; i <= n; i++) { 32 cin >> m; 33 a[i] = a[i-1] + m; 34 } 35 char p; 36 ll x, y, z; 37 for(int i = 1; i <= q; i++) { 38 cin >> p; 39 if(p == 'Q') { 40 cin >> x >> y; 41 cout <<(a[y] - a[x-1] + getsum(y) - getsum(x-1))<< endl; 42 } 43 else { 44 cin >> x >> y >> z; 45 update(x,z); 46 update(y+1,-z); 47 // for(int i = 1; i <= n; i++) { 48 // cout << b[i] << " " << c[i] << endl; 49 // } 50 } 51 } 52 return 0; 53 }