THIS IS CORRECT ANSWER
https://www.codechef.com/viewsolution/36769542
THIS IS HOW I DID
plz some one help me understanding logic , because when we update then the actual solution update function will only update one index , but we have to do update from u to v index
also while finding the point , when we have to find the index then we should do sum(n) - sum(n-1) but what the actual answer is finding is the sum of values from 1 to n position , but still the answer is working … plz… help
someone plz… help … i have just learnt the binary indexed tree
This solution is also implemented using Binary Indexed Tree(Fenwik Tree) .Might helps
#include<bits/stdc++.h>
#define ui unsigned int
#define ulld unsigned long long int
#define lld long long int
#define gc getchar_unlocked
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define MAX 1000000
#define MOD 1000000007
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define x getchar_unlocked()
#define y putchar_unlocked
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pair<int,int> > vpii;
typedef long long ll;
typedef vector<long long> vl;
typedef pair<long long,long long> pll;
typedef vector<pair<long long,long long> > vpll;
typedef vector<string> vs;
typedef long double ld;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
inline void inp( int &n )
{//fast input function
n=0;
int ch=x,sign=1;
while( ch < '0' || ch > '9' ){if(ch=='-')sign=-1; ch=x;}
while( ch >= '0' && ch <= '9' )
n=(n<<3)+(n<<1)+ ch-'0', ch=x;
n=n*sign;
}
int n;
//functions in structure ,new thing
struct ftree // fenwick tree
{
vl v;
void init()
{
v.assign(n+100001,0); // make all 0 at starting
}
void update(int i,int z)
{
while(i<=n)
{
v[i]+=z;
i+=(i & -i);
}
}
lld sum(int i)
{
lld r=0;
while(i)
{
r+=v[i];
i-=(i & -i);
}
return r;
}
};
int main()
{ int m,c;
inp(n);
inp(m);
inp(c);
ftree f;
f.init();
while(m--)
{ char s;
s=getchar_unlocked();
while(!(s=='Q'||s=='S'))
s=getchar();
if(s=='Q')
{ int u;
inp(u);
long long int ans=c;
ans+=(long long )(f.sum(u));
printf("%lld\n",ans);
}
else
{
int v,k,u;
inp(u);
inp(v);
inp(k);
f.update(u,k);
f.update(v+1,-k);
}
}
return 0;
}
This is my solution I was getting TLE becausing of using endl use '\n instead of endl
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define endl '\n'
//BINARY INDEXED TREE
//O(nlong(n)) for n no of updates and also o(longn) for each query
//basically we are creating an array of size of n when we update something the value at that index and also it affecting ancestors
//it's ancestors can get by using 2'complement of that number and of that number and subtract from orginal number
//basically it is if the original value is n that its ancestors are n=n-(n & -n)
//as do same for the query
int N=10e5+5;
struct ftree
{
vector<ll> v;
void init()
{
v.assign(N,0);
}
void update(ll i,ll val,ll n)
{
while(i<=n)
{
v[i]+=val;
i+=(i & -i);
}
}
ll getsum(ll i)
{
ll sum=0;
while(i>0)
{
sum+=v[i];
i-=(i & -i);
}
return sum;
}
};
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ftree f;
ll n,m,c;
cin>>n>>m>>c;
f.init();
for(int i=0;i<m;i++)
{
char c1;
cin>>c1;
if(c1=='S')
{
ll u,v,k;
cin>>u>>v>>k;
f.update(u,k,n);
f.update(v+1,-k,n);
}
else
{
ll pos;
cin>>pos;
ll ans=c;
ans+=f.getsum(pos);
cout<<ans<<endl;
}
}
}
thanks bro , endl played me … thanks again