poj 3486 A Simple Problem with Integers（树状数组第三种模板改段求段）

 1 /*
 2     树状数组第三种模板（改段求段）不解释！ 
       不明白的点这里：here！
 3 */
 4 #include<iostream>
 5 #include<cstring>
 6 #include<cstdio>
 7 #include<algorithm>
 8 #define N 100005
 9 using namespace std;
10 
11 typedef long long LL;
12 
13 LL ss[N], B[N], C[N];
14 
15 int n, m;
16 
17 void addB(int x, int k){//B[i]表示被1...i整体一共加了多少的总和 
18     for(int i=x; i<=n; i+=i&(-i))  B[i]+=x*k; 
19 }
20 
21 void addC(int x, int k){//1....x节点的每个节点的增量 
22     for(int i=x; i>0; i-=i&(-i))   C[i]+=k;
23 }
24 
25 LL sumB(int x){
26     LL s=0;
27     for(int i=x; i>0; i-=i&(-i)) s+=B[i];
28     return s;
29 }
30 
31 LL sumC(int x){//x节点总共的增量 
32     LL s=0;
33     for(int i=x; i<=n; i+=i&(-i)) s+=C[i];
34     return s;
35 }
36 
37 LL sum(int x){
38     return x==0 ? 0 : sumC(x)*x + sumB(x-1); 
39 }
40 
41 void update(int a, int b, int c){
42     addB(b, c);
43     addC(b, c);
44     if(a-1>0){
45         addB(a-1, -c); 
46         addC(a-1, -c);
47     }
48 }
49 
50 int main(){
51     int m;
52     while(scanf("%d%d", &n, &m)!=EOF){
53         for(int i=1; i<=n; ++i){
54             scanf("%lld", &ss[i]);
55             ss[i]+=ss[i-1];
56         } 
57         char ch[2];
58         int a, b, c;
59         while(m--){
60             scanf("%s", ch); 
61             if(ch[0]=='Q'){
62                 scanf("%d%d", &a, &b);
63                 printf("%lld
", ss[b]-ss[a-1]+sum(b)-sum(a-1));
64             }
65             else{
66                 scanf("%d%d%d", &a, &b, &c);
67                 update(a, b, c); 
68             }
69         }
70     }
71     return 0;
72 }