POJ 3468 A Simple Problem with Integers（线段树）

题意：给你n个数，进行两种操作，第一种是将a到b上所有元素都加上c，第二种是查询a到b上所有元素之和输出。

思路：线段树，以前写过博客，但是现在在重刷，风格改变，，所以重新写一篇。。。。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #define LL long long
 5 using namespace std ;
 6 
 7 LL lz[100010*4],p[100100*4] ;
 8 
 9 void pushup(int rt)
10 {
11     p[rt] = p[rt << 1] + p[rt << 1 | 1] ;
12 }
13 void pushdown(int rt,int m)
14 {
15     if(lz[rt])
16     {
17         lz[rt << 1] += lz[rt] ;
18         lz[rt << 1 | 1] += lz[rt] ;
19         p[rt << 1] += (m-m/2)*lz[rt] ;
20         p[rt << 1 | 1] += m/2 * lz[rt] ;
21         lz[rt] = 0 ;
22     }
23 }
24 void build(int l,int r,int rt)
25 {
26     lz[rt] = 0 ;
27     if(l == r)
28     {
29         scanf("%I64d%*c",&p[rt]) ;
30         return ;
31     }
32     int mid = (l+r) >> 1 ;
33     build(l,mid,rt << 1) ;
34     build(mid+1,r,rt << 1 | 1) ;
35     pushup(rt) ;
36 }
37 LL query(int L,int R,int l,int r,int rt)
38 {
39     LL sum = 0 ;
40     if(l >= L && R >= r)
41     {
42         return p[rt] ;
43     }
44     pushdown(rt,r-l+1) ;
45     int mid = (l+r) >> 1;
46     if(mid >= L)
47         sum += query(L,R,l,mid,rt << 1) ;
48     if(mid < R)
49         sum += query(L,R,mid+1,r,rt << 1 | 1) ;
50     return sum ;
51 }
52 void update(int L,int R, int l,int r,int sc,int rt)
53 {
54     if(l >= L && r <= R)
55     {
56         lz[rt] += sc ;
57         p[rt] += (r-l+1)*sc ;
58         return  ;
59     }
60     pushdown(rt,r-l+1) ;
61     int mid = (l+r) >> 1 ;
62     if(mid >= L)
63         update(L,R,l,mid,sc,rt << 1) ;
64     if(mid < R)
65         update(L,R,mid+1,r,sc,rt << 1 | 1) ;
66     pushup(rt) ;
67 }
68 int main()
69 {
70     int N,Q ,a,b;
71     LL c ;
72     char ch[3] ;
73     while(~scanf("%d %d",&N,&Q))
74     {
75         build(1,N,1) ;
76         for(int i = 0 ; i < Q ; i++)
77         {
78             scanf("%s",ch) ;
79             if(ch[0] == 'Q')
80             {
81                 scanf("%d %d",&a,&b) ;
82                 LL sum = query(a,b,1,N,1) ;
83                 printf("%I64d
",sum) ;
84             }
85             else
86             {
87                 scanf("%d %d %I64d",&a,&b,&c) ;
88                 update(a,b,1,N,c,1) ;
89             }
90         }
91     }
92     return 0 ;
93 }

View Code