POJ.3468 A Simple Problem with Integers

1.Problem
http://poj.org/problem?id=3468

2.Idea
Segment Tree

3.Source

 #define MAX_N 100000  
 #define MAX_Q 100000  
 const int DAT_SIZE = (1 << 18) - 1;  
 int N, Q;  
 int A[MAX_N];  
 char T[MAX_Q];  
 int L[MAX_Q], R[MAX_Q], X[MAX_Q];  
 ll datA[DAT_SIZE], datB[DAT_SIZE];  
 void add(int a, int b, int x, int k, int l, int r)  
 {  
      if (a <= l && r <= b) {  
           datA[k] += x;  
      }  
      else if(l < b && a < r) {  
           datB[k] += (min(b, r) - max(a, l)) * x;  
           add(a, b, x, k * 2 + 1, l, (l + r) / 2);  
           add(a, b, x, k * 2 + 2, (l + r) / 2, r);  
      }  
 }  
 ll sum(int a, int b, int k, int l, int r)  
 {  
      if (b <= l || r <= a) {  
           return 0;  
      }  
      else if (a <= l && r <= b) {  
           return datA[k] * (r - l) + datB[k];  
      }  
      else {  
           ll res = (min(b, r) - max(a, l)) * datA[k];  
           res += sum(a, b, k * 2 + 1, l, (l + r) / 2);  
           res += sum(a, b, k * 2 + 2, (l + r) / 2, r);  
           return res;  
      }  
 }  
 void solve()  
 {  
      for (int i = 0; i < N; i++) {  
           cin >> A[i];  
           add(i, i + 1, A[i], 0, 0, N);  
      }  
      for (int i = 0; i < Q; i++) {  
           int a, b, x;  
           char c;  
           scanf(" %c", &c);  
           if (c == 'C') {  
                scanf("%d %d %d", &a, &b, &x);  
                add(a - 1, b, x, 0, 0, N);  
           }  
           else {  
                scanf("%d %d", &a, &b);  
                printf("%lld\n", sum(a - 1, b, 0, 0, N));  
           }  
      }  
 }  
 int main()  
 {  
      scanf("%d%d", &N, &Q);  
      solve();  
      return 0;  
 }