/*
树状数组第三种模板（改段求段）不解释！
不明白的点这里：here！
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define N 100005
using namespace std;
typedef long long LL;
LL ss[N], B[N], C[N];
int n, m;
void addB(int x, int k){//B[i]表示被1...i整体一共加了多少的总和
for(int i=x; i<=n; i+=i&(-i)) B[i]+=x*k;
}
void addC(int x, int k){//1....x节点的每个节点的增量
for(int i=x; i>0; i-=i&(-i)) C[i]+=k;
}
LL sumB(int x){
LL s=0;
for(int i=x; i>0; i-=i&(-i)) s+=B[i];
return s;
}
LL sumC(int x){//x节点总共的增量
LL s=0;
for(int i=x; i<=n; i+=i&(-i)) s+=C[i];
return s;
}
LL sum(int x){
return x==0 ? 0 : sumC(x)*x + sumB(x-1);
}
void update(int a, int b, int c){
addB(b, c);
addC(b, c);
if(a-1>0){
addB(a-1, -c);
addC(a-1, -c);
}
}
int main(){
int m;
while(scanf("%d%d", &n, &m)!=EOF){
for(int i=1; i<=n; ++i){
scanf("%lld", &ss[i]);
ss[i]+=ss[i-1];
}
char ch[2];
int a, b, c;
while(m--){
scanf("%s", ch);
if(ch[0]=='Q'){
scanf("%d%d", &a, &b);
printf("%lld\n", ss[b]-ss[a-1]+sum(b)-sum(a-1));
}
else{
scanf("%d%d%d", &a, &b, &c);
update(a, b, c);
}
}
}
return 0;
}
本文转自 小眼儿 博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/3969029.html，如需转载请自行联系原作者
![[HDU7073] Integers Have Friends 2.0 -随机大法好](https://ucc.alicdn.com/pic/developer-ecology/57af2f40c29641aaac46af6b66998b9d.png?x-oss-process=image/resize,h_160,m_lfit)