I have been trying this problem which is supposed to be solved using fenwick trees
The data structure i used is a tree where all the leaves are the array and for every node the value is sum of values of children.
So we can calculate sum of the array between indices i and j in log n time.
But it is saying Wrong Answer.
Please help.
#include
#include <stdio.h>
#include
#include
#include
#define vi vector
#define pi pair<int,int>
#define si stack
typedef long long int ll;
using namespace std;
vector v(2097152,0);
ll sum (ll a,ll b)
{
ll res = 0;
//cout<<a<<" "<<b<<endl;
if (b == (a+1))
{
return v[b]+v[a];
}
while (a < b)
{
if (a%2 != 0)
{
res+=v[a];a++;}
if(b%2 == 0){res+=v[b];b--;}
if (a == b)break;
a/=2;
b/=2;
// cout<<a<<" "<<b<<endl;
// cout<<"REs "<<res<<endl;
}
res+=v[a];
return res;
}
int main ()
{
ll n,q;
cin >>n>>q;
ll var;
for (ll i = 0;i <n;i++)
{
scanf("%lld",&var);
//var = 1000;
v[i+1048576]=var;
ll w = (i+1048576)/2;
while(w >= 1)
{
v[w]=v[2*w]+v[2*w+1];
w/=2;
}
}
for(ll z =1;z <= q;z++)
{
char c;
cin >>c;
if (c == 'S')
{
ll i,j;
cin>>i>>j;
//cout<<i<<" "<<j<<endl;
//for(int i =0;i<5;i++)cout<<v[1048576+i]<<" ";
cout<<sum(1048576+i,1048576+j)<<endl;
}
if (c == 'G')
{
ll i,va;
cin>>i>>va;
v[i+1048576]+=va;
ll w = (i+1048576)/2;
while(w >= 1)
{
v[w]=v[2*w]+v[2*w+1];
w/=2;
}
}
if (c == 'T')
{
ll i,va;
cin>>i>>va;
v[i+1048576]-=va;
ll w = (i+1048576)/2;
while(w >= 1)
{
v[w]=v[2*w]+v[2*w+1];
w/=2;
}
}
}
}