poj3468A Simple Problem with Integers(线段树延时更新)

题意：
有n个整数A1,A2,……,An,给你两种操作，一个是给区间[l,r]的值都增加m,一个是问区间[l,r]的和是多少。

 1 #include <iostream>
 2 #include <cstdio>
 3 #define lson l,mid,i<<1
 4 #define rson mid+1,r,i<<1|1
 5 using namespace std;
 6 const int Ni = 100010;
 7 long long tree[Ni*3];
 8 long long add[Ni*3];
 9 int n;
10 void build(int l=1,int r=n,int i=1)
11 {
12     add[Ni]=0;
13     if(l==r)
14     {
15         scanf("%I64d",tree+i);
16         return ;
17     }
18     int mid=(l+r)>>1;
19     build(lson);
20     build(rson);
21     tree[i]=tree[i<<1]+tree[i<<1|1];
22 }
23 inline void pushdown(int l,int r,int i)
24 {
25     if(add[i])
26     {
27         add[i<<1]+=add[i];
28         add[i<<1|1]+=add[i];
29         int mid=(l+r)>>1;
30         tree[i<<1]+=(mid-l+1)*add[i];
31         tree[i<<1|1]+=(r-mid)*add[i];
32         add[i]=0;
33     }
34 }
35 void update(int ql,int qr,int val,int l=1,int r=n,int i=1)
36 {
37 
38     if(ql<=l&&r<=qr)
39     {
40         add[i]+=val;
41         tree[i]+=(r-l+1)*val;
42         return ;
43     }
44     int mid=(l+r)>>1;
45     pushdown(l,r,i);
46     if(ql<=mid) update(ql,qr,val,lson);
47     if(qr>mid) update(ql,qr,val,rson);
48     tree[i]=tree[i<<1]+tree[i<<1|1];
49 }
50 long long query(int ql,int qr,int l=1,int r=n,int i=1)
51 {
52 
53     long long ret=0;
54     if(ql<=l&&r<=qr)
55     {
56         return tree[i];
57     }
58     int mid=(l+r)>>1;
59     pushdown(l,r,i);
60     if(ql<=mid) ret+=query(ql,qr,lson);
61     if(qr>mid) ret+=query(ql,qr,rson);
62     return ret;
63 }
64 int main()
65 {
66     int m;
67     //freopen("fin.txt","r",stdin);
68     while(~scanf("%d%d",&n,&m))
69     {
70         build();
71         for(int i=0;i<m;i++)
72         {
73             char ch[5];
74             int ql,qr,val;
75             scanf("%s",ch);
76             if(ch[0]=='Q')
77             {
78                 scanf("%d%d",&ql,&qr);
79                 printf("%I64d\n",query(ql,qr));
80             }
81             else
82             {
83                 scanf("%d%d%d",&ql,&qr,&val);
84                 update(ql,qr,val);
85             }
86         }
87     }
88     return 0;
89 }

10 22
1 2 3 4 5 6 7 8 9 10
Q 4 4
C 1 10 3
C 6 10 3
C 6 9 3
C 8 9 -100
C 7 9 3
C 7 10 3
C 1 10 3
Q 6 10
Q 6 9
Q 8 9
Q 7 9
Q 7 10
Q 1 10
Q 2 4
C 3 6 3
Q 9 9
Q 1 1
Q 5 5
Q 6 6
Q 7 7
Q 6 8

5 5
1000000000 1000000000 1000000000 1000000000 1000000000
Q 1 2
Q 3 3
Q 5 5
C 1 2 1000000000
C 1 5 1000000000
C 1 5 1000000000
Q 1 2
Q 4 5

ans:
4
-82
-104
-147
-122
-100
-37
27
-73
7
14
21
25
-28
2000000000
1000000000
1000000000
8000000000
6000000000