The problem I'm trying to solve is: Problem I'm implementing Fenwick Trees in a 2D matrix. Also I've been using Fast i/o but I'm still getting a TLE. I'm not sure if this approach would work. Please help me with this. Thanks in advance. My Code:
#include <bits/stdc++.h>
using namespace std;
vector <long long> freq[1030];
long long n;
void update(long long x,long long y,long long val)
{
while(y<=n)
{
freq[x][y]+=val;
y = y + (y & -y);
}
}
long long sum(long long x,long long ind)
{
long long s=0;
while(ind>0)
{
s+=freq[x][ind];
ind = ind - (ind & -ind);
}
return s;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long long t;
scanf("%lld",&t);
while(t--)
{
scanf("%lld",&n);
for(long long i=0;i<=n;i++)
{
freq[i].clear();
freq[i].resize(n+5,0);
}
char s[100] ="hehe";
while(strcmp(s,"END")!=0)
{
scanf("%s",s);
if(strcmp(s,"SET")==0)
{
long long x,y,v;
scanf("%lld %lld %lld",&x, &y, &v);
x++;
y++;
update(x,y,v-freq[x][y]);
}
else if(strcmp(s,"SUM")==0)
{
long long ans=0;
long long x1,x2,y1,y2;
scanf("%lld %lld %lld %lld",&x1, &y1, &x2, &y2);
x1++;
y1++;
x2++;
y2++;
for(long long i=x1;i<=x2;i++)
{
ans+=sum(i,y2)-sum(i,y1-1);
}
printf("%lld\n",ans);
}
}
}
}
Your code is O(Q * N * log(N)) since if I query for (0, 0, n, n) every time, you will loop from (0, n) and BIT query from (0, n) for a total of O(NlogN). you can get around this with a 2D BIT. read more from the 2D BIT section of cp-algos.