Codechef - Funny Marbles

marble.cpp

//http://www.codechef.com/problems/MARBLEGF/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <map>
#include <vector>
#include <list>
#include <set>
#include <bitset>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <cmath>
#include <cassert>
#include <climits>

using namespace std;

#define LSOne(S) (S & (-S))

#define FOR(i,a,b) for(int i=a;i<b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define REP(i,n) FOR(i,0,n)

typedef vector<long long int> vi;

class FenwickTree {
private:
  vi ft;

public:
  FenwickTree() {}
  FenwickTree(int n) { ft.assign(n + 1, 0); }

  long long int rsq(int b) {                                     
    long long int sum = 0; for (; b; b -= LSOne(b)) sum += ft[b];
    return sum; }

  long long int rsq(int a, int b) {                             
    return rsq(b) - (a == 1 ? 0 : rsq(a - 1)); }

  void adjust(int k, long long int v) {                    
    for (; k < (int)ft.size(); k += LSOne(k)) ft[k] += v; }
};

int main(int argc, char *argv[]) {

    int n, q;
    long long int a[1000005];
    char querie;
    long long int x,y;

    scanf("%d %d", &n, &q);
    for(int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }

    FenwickTree ft(1000005);

    for(int i = 1; i <= n; i++) {
        ft.adjust(i,a[i]);
    }

    while(q--) {
        cin >> querie >> x >> y;
        x++;
        if(querie == 'S') {
            y++;
            printf("%lld\n", ft.rsq(x,y));
        } else if(querie == 'G') {
            a[x] += y;
            ft.adjust(x,y);
        } else if(querie == 'T') {
            if((a[x] - y) >= 0) {
                ft.adjust(x,-y);
                a[x] -= y;
            } else {
                y = a[x];
                ft.adjust(x,-y);
                a[x] = 0;
            }
        }
    }

    return 0;
}