区间更新，区间求和。C的时候在区间[a,b]之间，每个元素增加一个c。Q的时候求出[a,b]区间元素的和。
思路：线段树。增加一个增量属性add，更新到范围内的时候刷新add和value的值，这个时候不再向下传递，如果需要向下更新或者向下询问的时候，更新节点两个子树的add和value属性，这样需要用的到时候再更新会提高效率。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=100003;
long long sum;
inline int L(int r){return r<<1;}
inline int R(int r){return (r<<1)+1;}
inline int MID(int l,int r){return (l+r)>>1;}
typedef struct
{
int left,right;
long long value,add;
}node;
node tree[MAXN*4];
long long arr[MAXN];
void Update(int);
void Create(int l,int r,int root)
{
tree[root].left=l;
tree[root].right=r;
tree[root].add=0;
if(l==r) {tree[root].value=arr[l];return;}
int mid =MID(l,r);
Create(l,mid,L(root));
Create(mid+1,r,R(root));
tree[root].value=tree[L(root)].value+tree[R(root)].value;
}
void Add(int l,int r,long long v,int root)
{
if(l<=tree[root].left&&tree[root].right<=r)
{
tree[root].add+=v;
tree[root].value+=v*(tree[root].right-tree[root].left+1);
return;
}
Update(root);
if(tree[root].left==tree[root].right) {return;}
int mid=MID(tree[root].left,tree[root].right);
if(l>mid) Add(l,r,v,R(root));
else if(r<=mid) Add(l,r,v,L(root));
else
{
Add(l,mid,v,L(root));
Add(mid+1,r,v,R(root));
}
tree[root].value=tree[L(root)].value+tree[R(root)].value;
}
void Update(int node)//更新节点，把大区间的增值传给小区间，给小区间的值加上增量
{
if(tree[node].add)
{
tree[L(node)].add+=tree[node].add;//更新子树时会用到
tree[R(node)].add+=tree[node].add;
tree[L(node)].value+=(tree[L(node)].right-tree[L(node)].left+1)*tree[node].add;//这时候的值就是区间和
tree[R(node)].value+=(tree[R(node)].right-tree[R(node)].left+1)*tree[node].add;
tree[node].add=0;
}
}
void Solve(int l,int r,int root)
{
if(l<=tree[root].left&&tree[root].right<=r)
{
sum+=tree[root].value;
return;
}
Update(root);
if(tree[root].left==tree[root].right) return;
int mid=MID(tree[root].left,tree[root].right);
if(l>mid) Solve(l,r,R(root));
else if(r<=mid) Solve(l,r,L(root));
else
{
Solve(l,mid,L(root));
Solve(mid+1,r,R(root));
}
}
int main()
{
//freopen("input","r",stdin);
int m,n;
while(scanf("%d %d",&m,&n)!=EOF)
{
for(int i=1;i<=m;i++)
{
scanf("%lld",arr+i);
}
Create(1,m,1);
char c[2];
while(n--)
{
scanf("%s",c);
if('C'==c[0])
{
int l,f;
long long v;
scanf("%d %d %lld",&l,&f,&v);
Add(l,f,v,1);
}
else
{
int l,f;
scanf("%d %d",&l,&f);
sum=0;
Solve(l,f,1);
printf("%lld\n",sum);
}
}
}
return 0;
}