http://www.codechef.com/problems/MARBLEGF
code ////
#include<stdio.h>
#include<math.h>
using namespace std;
long long int getSumUtil(long long int *st, int ss, int se, int qs, int qe, int index)
{
if (qs <= ss && qe >= se)
return st[index];
if (se < qs || ss > qe)
return 0;
int mid = (ss+se)/2;
return getSumUtil(st, ss, mid, qs, qe, (index << 1)+1) + getSumUtil(st, mid+1, se, qs, qe, (index << 1)+2);
}
void updateValueUtil(long long int *st, int ss, int se, int i, int diff, int index)
{
if (i < ss || i > se)
return;
st[index] = st[index] + diff;
if (se != ss)
{
int mid = (ss+se)/2;
updateValueUtil(st, ss, mid, i, diff, (index << 1)+ 1);
updateValueUtil(st, mid+1, se, i, diff, (index << 1) + 2);
}
}
void updateValue(int arr[], long long int *st, int n, int i, int new_val)
{
int diff = new_val - arr[i];
arr[i] = new_val;
updateValueUtil(st, 0, n-1, i, diff, 0);
}
long long int getSum(long long int *st, int n, int qs, int qe)
{
return getSumUtil(st, 0, n-1, qs, qe, 0);
}
long long int constructSTUtil(int arr[], int ss, int se, long long int *st, int si)
{
if (ss == se)
{
st[si] = arr[ss];
return arr[ss];
}
int mid = (ss+se)/2;
st[si] = constructSTUtil(arr, ss, mid, st, si*2+1) + constructSTUtil(arr, mid+1, se, st, si*2+2);
return st[si];
}
long long int *constructST(int arr[], int n)
{
int x = (int)(ceil(log2(n)));
int max_size = 2*(int)pow(2, x) - 1;
long long int *st = new long long int[max_size];
constructSTUtil(arr, 0, n-1, st, 0);
return st;
}
int arr[1000000];
int main()
{ char ch;
int n, q;
scanf("%d %d", &n, &q);
for(int i=0;i<n;i++)
scanf("%d",&arr[i]);
long long int *st = constructST(arr, n);
for(int i=0;i<q;i++)
{
ch=getchar();
while(ch=='\n')
ch=getchar();
int x, y;
scanf("%d %d",&x,&y);
if(ch == 'S')
printf("%lld\n", getSum(st, n, x, y));
else if(ch == 'G')
updateValue(arr, st, n, x, arr[x]+y);
else
updateValue(arr, st, n, x, arr[x]-y);
}
return 0;
}