这是我的第一道线段树懒操作，2次TLE，6次WA之后，终于AC了。
其实题目本身没有那么难，不过因为是第一次写，所以很多细节都没注意到。
我在写另一道hdu上的题目的时候，我没有查资料，一直自己yy懒操作该是怎么样。当时我想的是应该是在结点里放一个flag，用来存储对这个结点的子树的更新信息。在更新的时候这个信息并不往下传递，仅仅只是存下来，在需要查询的时候再传递。实际上我想的基本没错，但是当时一个问题卡住我了，那就是，如果我需要查询左子树的值，这时候flag的值需要往左子树更新，那么树根上的flag的值就需要清0。但是右子树怎么办？
这个问题我一直没想到怎么解决，知道我看了别人的思路。。。。。原来只要将这个父节点的flag的值同时传递到它的左右子树就行了。亏我想了那么久，脑子抽筋了。
其他的操作就是线段树的常规操作做了一些小修改，没有什么特别值得一说的地方了。
#include<stdio.h>
#include<string.h>
#define N 100005
struct node
{
int x,y;
__int64 sum;
__int64 flag;
}a[N*3];
int b[N];
void Bulid_Tree(int t,int x,int y)
{
a[t].x=x;
a[t].y=y;
a[t].flag=0;
if(x==y)
{
a[t].sum=b[x];
return ;
}
int temp=t*2;
int mid=(x+y)/2;
Bulid_Tree(temp,x,mid);
Bulid_Tree(temp+1,mid+1,y);
a[t].sum=a[temp].sum+a[temp+1].sum;
return ;
}
void Update_Tree(int t,int x,int y,__int64 flag)
{
if(a[t].x==x&&a[t].y==y)
{
a[t].flag+=flag;
return ;
}
a[t].sum=a[t].sum+(y-x+1)*flag;
int temp=t*2;
int mid=(a[t].x+a[t].y)/2;
if(y<=mid)
Update_Tree(temp,x,y,flag);
else if(x>mid)
Update_Tree(temp+1,x,y,flag);
else
{
Update_Tree(temp,x,mid,flag);
Update_Tree(temp+1,mid+1,y,flag);
}
return ;
}
__int64 Find_Tree(int t,int x,int y)
{
__int64 sum=0;
if(a[t].x==x&&a[t].y==y)
return a[t].sum+(a[t].y-a[t].x+1)*a[t].flag;
int temp=t*2;
int mid=(a[t].x+a[t].y)/2;
a[temp].flag+=a[t].flag;
a[temp+1].flag+=a[t].flag;
a[t].sum=a[t].sum+(a[t].y-a[t].x+1)*a[t].flag;
a[t].flag=0;
if(y<=mid)
sum+=Find_Tree(temp,x,y);
else if(x>mid)
sum+=Find_Tree(temp+1,x,y);
else
{
sum+=Find_Tree(temp,x,mid);
sum+=Find_Tree(temp+1,mid+1,y);
}
return sum;
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
int i;
for(i=1;i<=n;i++)
scanf("%d",&b[i]);
Bulid_Tree(1,1,n);
getchar();
while(m--)
{
char c;
scanf("%c",&c);
if(c=='Q')
{
int x,y;
scanf("%d%d",&x,&y);
getchar();
printf("%I64d\n",Find_Tree(1,x,y));
}
else
{
int x,y;
__int64 z;
scanf("%d%d%I64d",&x,&y,&z);
getchar();
Update_Tree(1,x,y,z);
}
}
}
return 0;
}