poj 3468(线段树)

题意：给n个数字，从A_{1 …………}A_nm次命令，Q是查询，查询a到b的区间和，c是更新，从a到b每个值都增加x。
思路：这是一个很明显的线段树的题目，就是线段树的用区间更新就可以，我也是第一次用。。
 1 #include <stdio.h>
 2 #include <string.h>
 3 #define maxn 100050
 4 
 5 long long arra[ maxn ];
 6 
 7 struct note{      //要用long long 类型的，不然会爆数据的。
 8 
 9     long long sum,c;
10 
11 }segtree[ maxn * 4 ];
12 
13 void build(int root , int instart , int iend)    //插入操作。
14 {
15     segtree[ root ].c = 0;
16     if(instart == iend)
17         segtree[ root ].sum = arra[ instart ];
18     else
19     {
20         int mid = (instart + iend)/2;
21         build( root * 2 , instart ,mid );
22         build( root * 2 + 1 , mid + 1 , iend );
23         segtree[ root ].sum = segtree[ root * 2 ].sum + segtree[ root *2 +1 ].sum;
24     }
25 }
26 
27 void pushdown(int root,int sta , int en )    //延迟标记。
28 {
29     if(segtree[ root ].c != 0)
30     {
31         segtree[ root * 2 ].c += segtree[ root ].c;
32         segtree[ root * 2 + 1 ].c += segtree [ root ].c;
33         int mid = (sta + en) / 2;
34         segtree[ root * 2] .sum += segtree[ root ].c*( mid - sta + 1 );
35         segtree[ root * 2 + 1 ].sum += segtree[ root ].c *( en - mid );
36         segtree[ root ].c = 0;
37     }
38 }
39 
40 long long Find(int root , int ranges , int rangee , int goals ,int goale)     //查找。查找时也需要对延迟标记进行更新。
41 {
42     if( goals > rangee || goale < ranges)
43         return 0;
44     if( rangee <= goale && ranges >= goals)
45         return segtree[ root ].sum;
46     pushdown(root,ranges,rangee);
47     int mid = (rangee+ranges) / 2;
48     return Find(root * 2 , ranges , mid , goals ,goale)+ Find(root * 2 + 1, mid +1 , rangee , goals , goale );
49 }
50 
51 
52 
53 
54 void update(int root , int sta, int en,int x,int y,int val)          //更新。
55 {
56     if( x > en || y < sta)
57         return ;
58     if( x <= sta && y >= en)
59     {
60         segtree[ root ].sum += val*( en - sta + 1 ) ;
61         segtree[ root ].c += val ;
62         return ;
63     }
64         pushdown(root,sta,en);
65         int mid = ( sta + en ) / 2;
66             update ( root * 2 , sta , mid , x ,y ,val );
67             update ( root * 2 + 1, mid + 1 , en , x , y , val );
68         segtree [ root ].sum = segtree[ root * 2 ].sum + segtree[ root * 2 + 1 ].sum;
69 }
70 
71 
72 int main()
73 {
74     //freopen("in.txt","r",stdin);
75     int m,n,a,b,c;
76     char x;
77     scanf("%d%d",&m,&n);
78     for( int i = 1 ; i <= m ; i++ )
79         scanf("%lld",&arra[i]);
80         build(1,1,m);
81     for( int i = 1 ; i <= n ; i++ )
82     {
83         scanf("%s",&x);
84         if(x=='Q')
85         {
86             scanf("%d%d",&a,&b);
87             printf("%lld
",Find(1,1,m,a,b));
88         }
89         else
90         {
91             scanf("%d%d%d",&a,&b,&c);
92                 update(1,1,m,a,b,c);
93         }
94     }
95     return 0;
96 }