典型的一道基于lazy传递的线段树题目，这题和一般题目不同的地方在于，它的每次操作不是简单的覆盖线段，而是累加。记得第一次写的时候纠结了好久。

好的，既然是累加，那么如何传递lazy呢？答案是传递累加值！

为线段树加一个add域，表示该线段需要加几。如果某区间的add不为0，那么就将该区间的add传递给其子区间，并且跟新子区间的sum_val值。

解这题最关键的就是要能够分清楚啥东西要传递，传递下去将有什么影响，其他的都好说！整体来说还是蛮轻松的

1 #include
      
          2 #include
       
           3 #include
        
            4 using namespace std;   5   6 struct node   7 {
      8     int l;   9     int r;  10     __int64 add;  11     __int64 sum_val;  12 };  13  14 node tree[500000];  15 int n,m;  16 __int64 num[100001];  17  18 void build(int i,int l,int r)  19 {
     20     tree[i].l=l;  21     tree[i].r=r;  22     tree[i].add=0;  23     if(l==r)  24     {
     25         tree[i].sum_val=num[l];  26         return;  27     }  28     int mid=(l+r)/2;  29     build(2*i,l,mid);  30     build(2*i+1,mid+1,r);  31     tree[i].sum_val=tree[2*i].sum_val+tree[2*i+1].sum_val;  32 }  33  34 void updata(int i,int l,int r,__int64 w)  35 {
     36     if(tree[i].l>r || tree[i].r
         
          =l && tree[i].r<=r)  39     {
     40         tree[i].add+=w;  //注意是+=，因为这不是简单的覆盖  41         tree[i].sum_val+=(tree[i].r-tree[i].l+1)*w; //由于区间所有的值都需要加上w，那么自然整段区间就是加上(w*区间大小)了  42         return;  43     }  44     if(tree[i].add!=0)  45     {
     46         tree[2*i].add+=tree[i].add; //同上，注意是+=  47         tree[2*i+1].add+=tree[i].add;  48         tree[2*i].sum_val+=(tree[2*i].r-tree[2*i].l+1)*tree[i].add;  49         tree[2*i+1].sum_val+=(tree[2*i+1].r-tree[2*i+1].l+1)*tree[i].add;  50         tree[i].add=0;  51     }  52     updata(2*i,l,r,w);  53     updata(2*i+1,l,r,w);  54     tree[i].sum_val=tree[2*i].sum_val+tree[2*i+1].sum_val; //回溯跟新  55 }  56  57 __int64 ans;  58 void find(int i,int l,int r)  59 {
     60     if(tree[i].l>r || tree[i].r
          
           =l && tree[i].r<=r)  63     {
     64         ans+=tree[i].sum_val;  65         return;  66     }  67     if(tree[i].add!=0)  68     {
     69         tree[2*i].add+=tree[i].add;  70         tree[2*i+1].add+=tree[i].add;  71         tree[2*i].sum_val+=(tree[2*i].r-tree[2*i].l+1)*tree[i].add;  72         tree[2*i+1].sum_val+=(tree[2*i+1].r-tree[2*i+1].l+1)*tree[i].add;  73         tree[i].add=0;  74     }  75     find(2*i,l,r);  76     find(2*i+1,l,r);  77 }  78  79 int main()  80 {
     81     int i,a,b;  82     __int64 w;  83     char c;  84     freopen("in.txt","r",stdin);  85     while(scanf("%d%d",&n,&m)==2)  86     {
     87         for(i=1;i<=n;i++)  88         {
     89             scanf("%I64d",&num[i]);  90         }  91         build(1,1,n);  92         for(i=0;i