POJ 3468 A Simple Problem with Integers (线段树多点更新模板)

题意：

给定一个区间，每个区间有一个初值，然后给出Q个操作， C a b c是给[a,b]中每个数加上c， Q a b 是查询[a,b]的和
代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 using namespace std;
 4 const int maxn = 100000 + 7;
 5 struct{
 6     long long val, addMark;
 7 }segTree[maxn << 2];
 8 long long a[maxn];
 9 int n , m;
10 void build(int root, int l, int r){
11     segTree[root].addMark = 0;
12 
13     if(l == r){
14         segTree[root].val = a[l];
15         return;//记得return
16     }
17     int mid = (l+r) >> 1;
18     build(root*2, l,mid);
19     build(root*2+1, mid + 1, r);
20     segTree[root].val = segTree[root*2].val + segTree[root*2+1].val; //回溯时候更新root
21 }
22 void push_down(int root,int L, int R){//传入L， R是为了计算左右子树的和， 分别是(mid - L + 1)、(R-mid)
23     if(segTree[root].addMark != 0){
24         int mid = L + R >> 1;
25         segTree[root*2].addMark += segTree[root].addMark;
26         segTree[root*2+1].addMark += segTree[root].addMark;
27 
28         segTree[root*2].val += segTree[root].addMark * (mid - L + 1);
29         segTree[root*2+1].val += segTree[root].addMark * (R-mid);
30 
31         segTree[root].addMark = 0;
32     }
33 }
34 long long query(int root, int L, int R, int QL, int QR){
35     if(L > QR || R < QL) return 0;
36 
37     if(QL <= L && QR >= R) {
38         return segTree[root].val;
39     }
40     push_down(root,L,R);//如果要向下计算记得先pushdown
41     int mid = L + R >> 1;
42     return query(root*2,L,mid,QL,QR) + query(root*2+1,mid+1,R,QL,QR);
43 }
44 void update(int root, int L ,int R, int QL, int QR, int val){
45     if(L > QR || R < QL) return;
46 
47     if(QL <= L && QR >= R){
48 
49         segTree[root].val += val * (R-L+1);
50         segTree[root].addMark += val;
51         return;
52     }
53 
54 
55     push_down(root,L,R);//如果要向下计算记得先pushdown
56     int mid = L + R >> 1;
57     update(root*2, L, mid, QL , QR , val);
58     update(root*2+1,mid+1, R, QL,QR,val);
59     segTree[root].val = segTree[root*2].val + segTree[root*2+1].val;//回溯更新root
60 }
61 int main()
62 {
63 //    freopen("1.txt","r", stdin);
64     while(~scanf("%d %d", &n , &m)){
65     memset(segTree,0,sizeof(segTree));
66 
67     for(int i = 1; i <= n; i++){
68         scanf("%lld", &a[i]);
69     }
70     build(1,1,n);
71     while(m--){
72         char cho[30];
73         scanf("%s", cho);
74         int x, y;
75         scanf("%d %d", &x, &y);
76         if(cho[0] == 'C'){
77             int v;
78             scanf("%d", &v);
79             update(1,1,n,x,y,v);
80         }
81         else{
82             printf("%lld
",query(1,1,n,x,y));
83         }
84     }
85     }
86 }