selfcompiler's blog

2D BIT problem

By selfcompiler, 10 years ago, In English

I am trying to solve the problem MATSUM on spoj.I try it using 2D Binary Indexed Tree.But keep getting Time Limit Exceeded.If my approach to solve this problem is not good enough then please suggest another methods.If my approach is correct then please guide me how to get rid-off from TLE.

My code is below 

Your code here...
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<utility>
#include<map>
#include<stdlib.h>
#include<string.h>
using namespace std;

#define g getchar_unlocked()

int scan()//fast input output
{
    int t=0;
    char c;
    c=g;
    while(c<'0' || c>'9')
    c=g;
    while(c>='0' && c<='9')
    {
    t=(t<<3)+(t<<1)+c-'0';
    c=g;
    }//end fast input output
    return(t);
}

vector<int> Matrix[1026];
int N;  // MAXVAL for Binary indexed tree tree(1 based indexing)
void initialize()
{
     scanf("%d",&N);
     for(int i=0;i<N;i++)
      Matrix[i].resize(N+2);
     return ; 
}
int Freq_at_idx(int idx,int vec_idx)
{
    int sum=Matrix[vec_idx][idx];
    if(idx>0)
    {
     int z=idx-(idx&-idx);
     idx--;
     while(idx!=z)
     {
                  sum-=Matrix[vec_idx][idx];
                  idx-=(idx&-idx);
     }
             
    }
    return sum;
}
void update(int vec_idx,int idx,int v)
{
     while(idx<=N)
     {
                  Matrix[vec_idx][idx]+=v;
                  idx+=(idx&-idx);
     }
     return ;
}

// it gives the sum of all the elements from 1 to idx of vector Matrix[vec_idx]

int Cumilative_Freq(int vec_idx,int idx)
{
    int sum=0;
    while(idx>0)
    {
        sum+=Matrix[vec_idx][idx];
        idx-=(idx&-idx);
    }
    return sum;
}
void set_value(int x,int y,int v)
{
     int v1;
     v1=Freq_at_idx(y+1,x);
     v=v-v1;
     if(v==0)
      return ;
     update(x,y+1,v);
}
void get_sum(int x1,int y1,int x2,int y2)
{
     int sum=0;
     for(int i=x1;i<=x2;i++)
     {
             sum+=Cumilative_Freq(i,y2+1)-Cumilative_Freq(i,y1);
     }
     printf("%d\n",sum);
     return ;
}
int main()
{
    int x,y,v,x1,x2,y1,y2;
    char str[5];
    int tc;
    //scanf("%d",&tc);
    tc=scan();
    while(tc--)
    {
    initialize();
    scanf("%s",str);
    while(str[0]!='E')
    {
             if(str[1]=='E')
               {
                   //scanf("%d%d%d",&x,&y,&v);
                   x=scan();
                   y=scan();
                   v=scan();
                   set_value(x,y,v);
               } 
              else
              {
                   //scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
                   x1=scan();
                   y1=scan();
                   x2=scan();
                   y2=scan();
                   get_sum(x1,y1,x2,y2);
              }
              scanf("%s",str);    
     }
     for(int i=0;i<N;i++)
      Matrix[i].clear();
    }
    return 0;
}
  • Vote: I like it
  • -17
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Hi selfcompiler

This evidently TLE. When coding a 2D BIT, you want the query/update runtimes to be around (log N) ^ 2. In your get_sum method (which is the querying), you have a loop that runs through [x1, x2], which is linear. This makes querying N log N.

I recommend reading this topcoder blog: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees . It explains quite clearly on how to code 1D/2D BIT's in a clean and efficient way. Your code for this should be no longer than 50 lines.

Let me know if you are still stuck

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Hii bboy_drain i tried to impliment this but now i am getting WA , i try this problem from last 4 days . I am not able to find out the bug in my code would you like to take a look at my new code ? 

Your code here...
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
/* 
                2D -Binary Indexed Tree Implimentation
                1-Based indexing Tree 
*/

#define MAX_SIZE 1027
long long int Val[5];
char Type[50]; 
vector<long long int> Tree[MAX_SIZE];
int N;
int MAXVAL_X;
int MAXVAL_Y;
void initialize()
{
     scanf("%d",&N);
     MAXVAL_X=N;
     MAXVAL_Y=N;
     for(int i=1;i<=MAXVAL_X;i++)
       Tree[i].resize(MAXVAL_Y+2);  //AUTOMATICALLY INITIALIZE ALL VALUES TO ZERO(0)
     return ;
}
long long int row_sum(int row_idx,int y)  //cumilative sum of row =row_idx from index=1 to index=y [1,y] inclusive 
{
    long long int sum=0;
    while(y>0)
    {
              sum+=Tree[row_idx][y];
              y-=(y&-y);
    }
    return sum;
}
long long int value_at_x_y(int x,int y)
{
    long long int sum1=0;
    sum1=row_sum(x,y)-row_sum(x,y-1);
    return sum1;
}
void update_row(int row_idx,int col_idx,long long int value)
{
     while(col_idx<=MAXVAL_Y)
     {
         Tree[row_idx][col_idx]+=value;
         col_idx+=(col_idx&-col_idx);
     }
     return ;
}
void Tree_Update(int x,int y,long long int value)
{
     value=value-value_at_x_y(x,y);
     if(value==0)
     return ;
     while(x<=MAXVAL_X)
     {
                       update_row(x,y,value);
                       x+=(x&-x);
     }
     return ;
}
long long int Corner_Matsum(int x,int y)
{
	long long int sum=0;
	while(x>0)
	{
		sum+=row_sum(x,y);
		x-=x&-x;
	}
	return sum;
}
long long int Tree_Sum(int x1,int y1,int x2,int y2)
{
    long long int sum1=0;  //sum up 0  to x1-1
    long long int sum2=0;  // sum up 0 to x2
    long long int sum3=0;
    long long int sum4=0;
    long long int sum=0;
    sum4=Corner_Matsum(x2,y2);
    sum1=Corner_Matsum(x1,y1-1);
    sum3=Corner_Matsum(x2,y1-1);
    sum2=Corner_Matsum(x1-1,y2);
    sum=sum4+sum1-sum2-sum3;
    return sum;
}
void set_Val()
{
     int f=0;
     for(int i=4;Type[i];i++)
     {
             if(Type[i]==' ')
             {
                           f++;
                           continue;
             }
              Val[f]=Val[f]*10+Type[i]-48;
     }
     return ;
}
int main()
{
    int tc;
    char c;
    scanf("%d",&tc);
  
    while(tc--)
    {
               initialize();
               c=getchar();
              
               scanf("%[^\n]s",Type);
               //printf("%s\n",Type);
               while(1)
               {
                 if(Type[0]=='E')
                   break;
               Val[0]=0;
               Val[1]=0;
               Val[2]=0;
               Val[3]=0;
               Val[4]=0;
                 set_Val();//set operation  fill Val[] array 
                if(Type[1]=='E')
                {
                     Tree_Update(Val[0]+1,Val[1]+1,Val[2]);          //update Tree            
                }
               else if(Type[1]=='U')
               {
                    printf("%lld\n",Tree_Sum(Val[0]+1,Val[1]+1,Val[2]+1,Val[3]+1));
               }
               c=getchar();
               scanf("%[^\n]s",Type);
               //printf("%s\n",Type);
              }
               printf("\n");
               for(int i=1;i<=N;i++)
                Tree[i].clear();
    }
    return 0;
    
}
→ Reply