區(qū)間更新，區(qū)間求和。C的時(shí)候在區(qū)間[a,b]之間，每個(gè)元素增加一個(gè)c。Q的時(shí)候求出[a,b]區(qū)間元素的和。
思路：線段樹(shù)。增加一個(gè)增量屬性add，更新到范圍內(nèi)的時(shí)候刷新add和value的值，這個(gè)時(shí)候不再向下傳遞，如果需要向下更新或者向下詢問(wèn)的時(shí)候，更新節(jié)點(diǎn)兩個(gè)子樹(shù)的add和value屬性，這樣需要用的到時(shí)候再更新會(huì)提高效率。
#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)//更新節(jié)點(diǎn)，把大區(qū)間的增值傳給小區(qū)間，給小區(qū)間的值加上增量
{
if(tree[node].add)
{
tree[L(node)].add+=tree[node].add;//更新子樹(shù)時(shí)會(huì)用到
tree[R(node)].add+=tree[node].add;
tree[L(node)].value+=(tree[L(node)].right-tree[L(node)].left+1)*tree[node].add;//這時(shí)候的值就是區(qū)間和
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;
}