SPOJ PROBLEM 1029 : MATRIX SUMMATION (MATSUM)

Problem Link: http://www.spoj.com/problems/MATSUM/

Serously Hard to get an AC using segment tree!!

2-D Binary Indexed Tree/Fenwick Tree Problem
Just like 1-D BIT we have to go in both x as well as y co-ordinate axis

2-D BIT QUERIES FOR FENWICK TREE

update_query(x,y,MAX)
       while(x<=MAX)
       {
            ty = y;
           while(ty <= MAX)   //For each y of x
          {
              a[x][ty] += val;
              ty += (ty & -ty);
          }
          x += (x & -x);
      }

read_query(x,y) 
       sum=0;
       while(x!=0)
       {
          ty = y;
          while(ty!=0)
         {
            sum+=a[x][ty];
            ty-=(ty & -ty);
         }
        x-=(x & -x);
       }

To finally read queries:
          .  .   .  .  .  .  .  .  .  .  .
          .  .   (x1,y1). .  .  .  .  .  .
          .  .   .  .  .  .  .  .  .  .  .
          .  .   .  .  .  .  .(x2,y2) .  .

read_query(x2,y2)-read_query(x1-1,y2)-read_query(x2,y1-1)
+ read(x1-1,y1-1)  //same part subtracted twice 

Basic Exclusion and Inclusion Principle