Блог пользователя Xenomorphing_19

Автор Xenomorphing_19, история, 4 года назад, По-английски

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);
            }
        }
    }
}
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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.