poj 3468 线段树，延迟标记法

http://poj.org/problem?id=3468

绝对称的上经典的线段树题；我又错了好几次；我主要错在了2个思维误区；

1，标记的时候没想到把不符合的节点的值加以改变，这样的话，如果搜索此节点的话，此节点没啥变化，导致错误；

2；在value传值的时候，一定要不论此值是否为0，一定传下去，因为有可能刚才是为！0，中间位0，如果都传下去，不会产生影响，否者会出错

一下是我的代码

#include<stdio.h>
 #include<stdlib.h>
 #include<string.h>
 #include<math.h>
 #include<iostream>
 #include<algorithm>
 using namespace std;


 const __int64 sizen=110000;
 struct ele
 {
     __int64 left;
     __int64 right;
     __int64 value;
     __int64 sum;
 }p[sizen*4];
 __int64 arr[sizen];


 void build(__int64 L,__int64 R,__int64 step)
 {
     p[step].value=0;
     p[step].left=L;
     p[step].right=R;
     if(L==R)
         p[step].sum=arr[L];
     else
     {
         __int64 Mid=(L+R)>>1;
         build(L,Mid,2*step);
         build(Mid+1,R,2*step+1);
         p[step].sum=p[step*2].sum+p[step*2+1].sum;
     }
 }


 void update(__int64 x,__int64 y,__int64 z,__int64 step)
 {
     if(p[step].left==x&&p[step].right==y)
         p[step].value+=z;
     else
     {
         p[step].sum+=(y-x+1)*z;
         __int64 Mid=(p[step].left+p[step].right)>>1;
         if(y<=Mid)
             update(x,y,z,2*step);
         else
         if(x>=Mid+1)
             update(x,y,z,2*step+1);
         else
         {
             update(x,Mid,z,2*step);
             update(Mid+1,y,z,2*step+1);
         }
     }
 }


 __int64 summ(__int64 x,__int64 y,__int64 step)
 {
     if(p[step].left==x&&p[step].right==y)
         return p[step].sum+(y-x+1)*p[step].value;
     else
     {
         p[step*2].value+=p[step].value;
         p[step*2+1].value+=p[step].value;
         p[step].sum+=(p[step].right-p[step].left+1)*p[step].value;
         p[step].value=0;
         __int64 Mid=(p[step].left+p[step].right)>>1;
         if(y<=Mid)
             return summ(x,y,2*step);
         else
         if(x>=Mid+1)
             return summ(x,y,2*step+1);
         else
             return summ(x,Mid,2*step)+summ(Mid+1,y,2*step+1);
     }
 }


 int main()
 {
     __int64 N,Q;
     __int64 i;
     __int64 x,y,z;
     char c;
     while(scanf("%I64d%I64d",&N,&Q)!=EOF)
     {
         for(i=1;i<=N;i++)
             scanf("%I64d",&arr[i]);
         build(1,N,1);
         while(Q--)
         {
             cin>>c;
             if(c=='Q')
             {
                 scanf("%I64d%I64d",&x,&y);
                 printf("%I64d\n",summ(x,y,1));
             }
             else
             {
                 scanf("%I64d%I64d%I64d",&x,&y,&z);
                 update(x,y,z,1);
             }
         }
     }
     return 0;
 }

【文章原创作者：阿里云代理商 http://www.558idc.com/aliyun.html 网络转载请说明出处】