poj 3468 线段树成段增加

比之前更明白了线段树的延迟更新，思想我感觉是，只更新到能交差的节点，不用更新到底，算是一种“偷懒”吧。我反正是一想这句话就懂了。

好了，代码风格都是一样的都是学习NotOnlySuccess的【完全版线段树】的风格。ps.我更喜欢res来表示结果。

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

 1 #include <stdio.h>
 2 #define lson l,m,rt<<1
 3 #define rson m+1,r,rt<<1|1
 4 #define maxn 100000+100
 5 #define ll long long 
 6 ll sum[maxn<<2];
 7 ll add[maxn<<2];  //add adapt sum
 8 void PushUp(int rt)
 9 {
10     sum[rt]=sum[rt<<1]+sum[rt<<1|1];
11 }
12 void PushDown(int rt,int l)
13 {
14     if(add[rt])
15     {
16         add[rt<<1]+=add[rt];
17         add[rt<<1|1]+=add[rt];
18         sum[rt<<1]+=add[rt]*(ll)(l-(l>>1));
19         sum[rt<<1|1]+=add[rt]*(ll)(l>>1);
20         add[rt]=0;
21     }
22 }
23 void build(int l,int r,int rt)
24 {
25     add[rt]=0;
26     if(l==r)
27     {
28         scanf("%lld",&sum[rt]);
29         return;
30     }
31     int m=(l+r)>>1;
32     build(lson);    build(rson);
33     PushUp(rt);
34 }
35 void update(int L,int R,int c,int l,int r,int rt)
36 {
37     if(L<=l&&r<=R)
38     {
39         add[rt]+=c;
40         sum[rt]+=(ll)c*(r-l+1);
41         return;
42     }
43     PushDown(rt,r-l+1);
44     int m=(l+r)>>1;
45     if(L<=m)
46         update(L,R,c,lson);
47     if(R>m)
48         update(L,R,c,rson);
49     PushUp(rt);
50 }
51 ll query(int L,int R,int l,int r,int rt)
52 {
53     if(L<=l&&r<=R)
54     {
55         return sum[rt];
56     }
57     PushDown(rt,r-l+1);
58     int m=(l+r)>>1;
59     ll res=0;
60     if(L<=m)
61         res=res+query(L,R,lson);
62     if(R>m)
63         res=res+query(L,R,rson);
64     return res;
65 }
66 int main()
67 {
68     int n,q;
69     char c;
70     int t1,t2,t3;
71     while(~scanf("%d%d",&n,&q))
72     {
73         build(1,n,1);
74         while(q--)
75         {
76         scanf("%*c%c",&c);
77         if(c=='Q')
78         {
79             scanf("%d%d",&t1,&t2);
80             printf("%lld\n",query(t1,t2,1,n,1));
81         }
82         if(c=='C')
83         {
84             scanf("%d%d%d",&t1,&t2,&t3);
85             update(t1,t2,t3,1,n,1);
86         }
87         }
88     }
89     return 0;
90 }