题意就是给了一序列的数...然后不断的问一段的值或者在一段上每个数加一个数...输出每次询问的值....
初看这题感觉就是最一般的线段树成段更新的应用...但下手后发现很多细节...对于一向很粗心的我调了很久才给调出来...成段更新前一文已经提到过..这里再通过这一题补充一些很值得注意的地方:
1、前一个题因为只有最后才要输出一段的总和...所以省去了GetSum的过程...这一题写的时候GetSum就写出了错误...充分理解了成段更新线段树的原理后...能知道只要访问到了一个点..不论是更新的时候还是求和的时候访问到...都应该有PushDown...将值给推下去....一定要注意...
2、这一题和上一题不同的是不是将一段数变为一段另外的数...而是将一段数的每个数加上一个数..这里的话很多地方就不是“=”了..而是"+="...col更新..sum除了sum=sum左+sum(右)..其余都是+=进行更新...
3、数据范围...要注意一段的合会爆int的...所以有几个地方要用long long来处理...
Program :
#include<iostream>
using namespace std;
long long sum[400001],col[400001],k;
int N,Q,a,b;
char c;
void build(int l,int r,long long sp)
{
if (l==r)
{
scanf("%I64d",&sum[sp]);
return;
}
int Mid=(l+r)/2;
build(l,Mid,sp*2);
build(Mid+1,r,sp*2+1);
sum[sp]=sum[sp*2]+sum[sp*2+1];
}
void PushDown(int sp,long long m)
{
if (col[sp])
{
col[sp*2]+=col[sp];
col[sp*2+1]+=col[sp];
sum[sp*2]+=(m-m/2)*col[sp];
sum[sp*2+1]+=m/2*col[sp];
col[sp]=0;
}
}
void Update(int L,int R,long long data,int l,int r,int sp)
{
if (L<=l && R>=r)
{
col[sp]+=data;
sum[sp]+=(long long)data*(r-l+1);
return;
}
PushDown(sp,r-l+1);
int Mid=(l+r)/2;
if (Mid>=L) Update(L,R,data,l,Mid,sp*2);
if (Mid< R) Update(L,R,data,Mid+1,r,sp*2+1);
sum[sp]=sum[sp*2]+sum[sp*2+1];
}
long long GetSum(int L,int R,int l,int r,int sp)
{
long long ans=0;
if (L<=l && R>=r) return sum[sp];
PushDown(sp,r-l+1); //!!! 更新和求和时都要PushDown
int Mid=(l+r)/2;
if (Mid>=L) ans+=GetSum(L,R,l,Mid,sp*2);
if (Mid< R) ans+=GetSum(L,R,Mid+1,r,sp*2+1);
return ans;
}
int main()
{
freopen("3468.in","r",stdin);
freopen("3468.out","w",stdout);
scanf("%d%d",&N,&Q);
memset(sum,0,sizeof(sum));
memset(col,0,sizeof(col));
build(1,N,1);
while (Q--)
{
scanf("\n%c%d%d",&c,&a,&b);
if (c=='C')
{
scanf("%I64d",&k);
Update(a,b,k,1,N,1);
}
else printf("%I64d\n",GetSum(a,b,1,N,1));
}
return 0;
}