poj 3468 A Simple Problem with Integers（线段树—

poj 3468 A Simple Problem with Integers（线段树——成段更新问题）

代码：
View Code
 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 __int64 s[400010];
 5 __int64 t[400010];//延迟数组，标记
 6 void push(int w)
 7 {
 8     s[w]=s[w*2]+s[w*2+1];
 9 }
10 void pushdown(int w, int d)
11 {
12     if(t[w])//如果延迟，向下更新
13     {
14         t[w*2]+=t[w];
15         t[w*2+1]+=t[w];
16         s[w*2]+=(t[w]*(d-(d/2)));
17         s[w*2+1]+=t[w]*(d/2);
18         t[w]=0;//去除标记
19     }
20 }
21 void build(int l,int r,int w)
22 {
23     t[w]=0;
24     if(l==r)
25     {
26         scanf("%I64d",&s[w]);
27         return ;
28     }
29     int m=(l+r)/2;
30     build(l,m,w*2);
31     build(m+1,r,w*2+1);
32     push(w);
33 }
34 void add(int l,int r,int L,int R,int num,int w)
35 {
36     if(L<=l&&R>=r)  //执行一次便返回，但不一定是叶子节点
37     {
38         t[w]+=num;
39         s[w]+=num*(r-l+1);
40         return ;
41     }
42     pushdown(w,r-l+1);//更新
43     int m=(l+r)/2;
44     if(L<=m)
45     add(l,m,L,R,num,w*2);
46     if(R>m)
47     add(m+1,r,L,R,num,w*2+1);
48     push(w);
49 }
50 __int64 query(int l,int r,int L,int R,int w)
51 {
52     if(L<=l&&R>=r)
53     {
54         return s[w];
55     }
56     pushdown(w,r-l+1);//更新
57     int m=(l+r)/2;
58     __int64 res=0;
59     if(L<=m)
60     res+=query(l,m,L,R,w*2);
61     if(R>m)
62     res+=query(m+1,r,L,R,w*2+1);
63     return res;
64 }
65 int main()
66 {
67     int m,n,i,a,b,c;
68     char str;
69     scanf("%d%d",&n,&m);
70     build(1,n,1);
71 
72     for(i=1;i<=m;i++)
73     {
74         scanf("%*c%c",&str);
75         if(str=='Q')
76         {
77             scanf("%d%d",&a,&b);
78             printf("%I64d\n",query(1,n,a,b,1));
79         }
80         else
81         {
82             scanf("%d%d%d",&a,&b,&c);
83             add(1,n,a,b,c,1);
84         }
85     }
86     return 0;
87 }