Two Dimensional Binary Indexed Tree or Fenwick Tree

Last Updated : 30 Nov, 2023

We know that to answer range sum queries on a 1-D array efficiently, binary indexed tree (or Fenwick Tree) is the best choice (even better than segment tree due to less memory requirements and a little faster than segment tree).

Can we answer sub-matrix sum queries efficiently using Binary Indexed Tree ?

The answer is yes. This is possible using a 2D BIT which is nothing but an array of 1D BIT.

Algorithm:

We consider the below example. Suppose we have to find the sum of all numbers inside the highlighted area:

fenwick tree

We assume the origin of the matrix at the bottom – O.Then a 2D BIT exploits the fact that-

Sum under the marked area = Sum(OB) - Sum(OD) - 
                            Sum(OA) + Sum(OC)

In our program, we use the getSum(x, y) function which finds the sum of the matrix from (0, 0) to (x, y).
Hence the below formula :

Sum under the marked area = Sum(OB) - Sum(OD) - 
                            Sum(OA) + Sum(OC) 

The above formula gets reduced to,

Query(x1,y1,x2,y2) = getSum(x2, y2) - 
                     getSum(x2, y1-1) - 
                     getSum(x1-1, y2) + 
                     getSum(x1-1, y1-1)

where,
x1, y1 = x and y coordinates of C
x2, y2 = x and y coordinates of B
The updateBIT(x, y, val) function updates all the elements under the region – (x, y) to (N, M) where,
N = maximum X co-ordinate of the whole matrix.
M = maximum Y co-ordinate of the whole matrix.
The rest procedure is quite similar to that of 1D Binary Indexed Tree.

Below is the C++ implementation of 2D indexed tree

C++

/* C++ program to implement 2D Binary Indexed Tree
 
2D BIT is basically a BIT where each element is another BIT.
Updating by adding v on (x, y) means it's effect will be found
throughout the rectangle [(x, y), (max_x, max_y)],
and query for (x, y) gives you the result of the rectangle
[(0, 0), (x, y)], assuming the total rectangle is
[(0, 0), (max_x, max_y)]. So when you query and update on
this BIT,you have to be careful about how many times you are
subtracting a rectangle and adding it. Simple set union formula
works here.
 
So if you want to get the result of a specific rectangle
[(x1, y1), (x2, y2)], the following steps are necessary:
 
Query(x1,y1,x2,y2) = getSum(x2, y2)-getSum(x2, y1-1) -
                     getSum(x1-1, y2)+getSum(x1-1, y1-1)
 
Here 'Query(x1,y1,x2,y2)' means the sum of elements enclosed
in the rectangle with bottom-left corner's co-ordinates
(x1, y1) and top-right corner's co-ordinates - (x2, y2)
 
Constraints -> x1<=x2 and y1<=y2
 
    /\
 y  |
    |           --------(x2,y2)
    |          |       |
    |          |       |
    |          |       |
    |          ---------
    |       (x1,y1)
    |
    |___________________________
   (0, 0)                   x-->
 
In this program we have assumed a square matrix. The
program can be easily extended to a rectangular one. */
 
#include<bits/stdc++.h>
using namespace std;
 
#define N 4 // N-->max_x and max_y
 
// A structure to hold the queries
struct Query
{
    int x1, y1; // x and y co-ordinates of bottom left
    int x2, y2; // x and y co-ordinates of top right
};
 
// A function to update the 2D BIT
void updateBIT(int BIT[][N+1], int x, int y, int val)
{
    for (; x <= N; x += (x & -x))
    {
        // This loop update all the 1D BIT inside the
        // array of 1D BIT = BIT[x]
        for (int yy=y; yy <= N; yy += (yy & -yy))
            BIT[x][yy] += val;
    }
    return;
}
 
// A function to get sum from (0, 0) to (x, y)
int getSum(int BIT[][N+1], int x, int y)
{
    int sum = 0;
 
    for(; x > 0; x -= x&-x)
    {
        // This loop sum through all the 1D BIT
        // inside the array of 1D BIT = BIT[x]
        for(int yy=y; yy > 0; yy -= yy&-yy)
        {
            sum += BIT[x][yy];
        }
    }
    return sum;
}
 
// A function to create an auxiliary matrix
// from the given input matrix
void constructAux(int mat[][N], int aux[][N+1])
{
    // Initialise Auxiliary array to 0
    for (int i=0; i<=N; i++)
        for (int j=0; j<=N; j++)
            aux[i][j] = 0;
 
    // Construct the Auxiliary Matrix
    for (int j=1; j<=N; j++)
        for (int i=1; i<=N; i++)
            aux[i][j] = mat[N-j][i-1];
 
    return;
}
 
// A function to construct a 2D BIT
void construct2DBIT(int mat[][N], int BIT[][N+1])
{
    // Create an auxiliary matrix
    int aux[N+1][N+1];
    constructAux(mat, aux);
 
    // Initialise the BIT to 0
    for (int i=1; i<=N; i++)
        for (int j=1; j<=N; j++)
            BIT[i][j] = 0;
 
    for (int j=1; j<=N; j++)
    {
        for (int i=1; i<=N; i++)
        {
            // Creating a 2D-BIT using update function
            // everytime we/ encounter a value in the
            // input 2D-array
            int v1 = getSum(BIT, i, j);
            int v2 = getSum(BIT, i, j-1);
            int v3 = getSum(BIT, i-1, j-1);
            int v4 = getSum(BIT, i-1, j);
 
            // Assigning a value to a particular element
            // of 2D BIT
            updateBIT(BIT, i, j, aux[i][j]-(v1-v2-v4+v3));
        }
    }
 
    return;
}
 
// A function to answer the queries
void answerQueries(Query q[], int m, int BIT[][N+1])
{
    for (int i=0; i<m; i++)
    {
        int x1 = q[i].x1 + 1;
        int y1 = q[i].y1 + 1;
        int x2 = q[i].x2 + 1;
        int y2 = q[i].y2 + 1;
 
        int ans = getSum(BIT, x2, y2)-getSum(BIT, x2, y1-1)-
                  getSum(BIT, x1-1, y2)+getSum(BIT, x1-1, y1-1);
 
        printf ("Query(%d, %d, %d, %d) = %d\n",
                q[i].x1, q[i].y1, q[i].x2, q[i].y2, ans);
    }
    return;
}
 
// Driver program
int main()
{
    int mat[N][N] = {{1, 2, 3, 4},
                    {5, 3, 8, 1},
                    {4, 6, 7, 5},
                    {2, 4, 8, 9}};
 
    // Create a 2D Binary Indexed Tree
    int BIT[N+1][N+1];
    construct2DBIT(mat, BIT);
 
    /* Queries of the form - x1, y1, x2, y2
       For example the query- {1, 1, 3, 2} means the sub-matrix-
    y
    /\
 3  |       1 2 3 4      Sub-matrix
 2  |       5 3 8 1      {1,1,3,2}      --->     3 8 1
 1  |       4 6 7 5                                 6 7 5
 0  |       2 4 8 9
    |
  --|------ 0 1 2 3 ----> x
    |
 
    Hence sum of the sub-matrix = 3+8+1+6+7+5 = 30
 
    */
 
    Query q[] = {{1, 1, 3, 2}, {2, 3, 3, 3}, {1, 1, 1, 1}};
    int m = sizeof(q)/sizeof(q[0]);
 
    answerQueries(q, m, BIT);
 
    return(0);
}

Java

/* Java program to implement 2D Binary Indexed Tree 
 
2D BIT is basically a BIT where each element is another BIT. 
Updating by adding v on (x, y) means it's effect will be found 
throughout the rectangle [(x, y), (max_x, max_y)], 
and query for (x, y) gives you the result of the rectangle 
[(0, 0), (x, y)], assuming the total rectangle is 
[(0, 0), (max_x, max_y)]. So when you query and update on 
this BIT,you have to be careful about how many times you are 
subtracting a rectangle and adding it. Simple set union formula 
works here. 
 
So if you want to get the result of a specific rectangle 
[(x1, y1), (x2, y2)], the following steps are necessary: 
 
Query(x1,y1,x2,y2) = getSum(x2, y2)-getSum(x2, y1-1) - 
                    getSum(x1-1, y2)+getSum(x1-1, y1-1) 
 
Here 'Query(x1,y1,x2,y2)' means the sum of elements enclosed 
in the rectangle with bottom-left corner's co-ordinates 
(x1, y1) and top-right corner's co-ordinates - (x2, y2) 
 
Constraints -> x1<=x2 and y1<=y2 
 
    /\ 
y | 
    |     --------(x2,y2) 
    |     | | 
    |     | | 
    |     | | 
    |     --------- 
    | (x1,y1) 
    | 
    |___________________________ 
(0, 0)             x--> 
 
In this program we have assumed a square matrix. The 
program can be easily extended to a rectangular one. */
class GFG
{ 
static final int N = 4; // N-.max_x and max_y 
 
// A structure to hold the queries 
static class Query 
{ 
    int x1, y1; // x and y co-ordinates of bottom left 
    int x2, y2; // x and y co-ordinates of top right 
 
        public Query(int x1, int y1, int x2, int y2)
        {
            this.x1 = x1;
            this.y1 = y1;
            this.x2 = x2;
            this.y2 = y2;
        }
         
}; 
 
// A function to update the 2D BIT 
static void updateBIT(int BIT[][], int x,
                      int y, int val) 
{ 
    for (; x <= N; x += (x & -x)) 
    { 
        // This loop update all the 1D BIT inside the 
        // array of 1D BIT = BIT[x] 
        for (; y <= N; y += (y & -y)) 
            BIT[x][y] += val; 
    } 
    return; 
} 
 
// A function to get sum from (0, 0) to (x, y) 
static int getSum(int BIT[][], int x, int y) 
{ 
    int sum = 0; 
 
    for(; x > 0; x -= x&-x) 
    { 
        // This loop sum through all the 1D BIT 
        // inside the array of 1D BIT = BIT[x] 
        for(; y > 0; y -= y&-y) 
        { 
            sum += BIT[x][y]; 
        } 
    } 
    return sum; 
} 
 
// A function to create an auxiliary matrix 
// from the given input matrix 
static void constructAux(int mat[][], int aux[][]) 
{ 
    // Initialise Auxiliary array to 0 
    for (int i = 0; i <= N; i++) 
        for (int j = 0; j <= N; j++) 
            aux[i][j] = 0; 
 
    // Construct the Auxiliary Matrix 
    for (int j = 1; j <= N; j++) 
        for (int i = 1; i <= N; i++) 
            aux[i][j] = mat[N - j][i - 1]; 
 
    return; 
} 
 
// A function to construct a 2D BIT 
static void construct2DBIT(int mat[][],
                           int BIT[][]) 
{ 
    // Create an auxiliary matrix 
    int [][]aux = new int[N + 1][N + 1]; 
    constructAux(mat, aux); 
 
    // Initialise the BIT to 0 
    for (int i = 1; i <= N; i++) 
        for (int j = 1; j <= N; j++) 
            BIT[i][j] = 0; 
 
    for (int j = 1; j <= N; j++) 
    { 
        for (int i = 1; i <= N; i++) 
        { 
            // Creating a 2D-BIT using update function 
            // everytime we/ encounter a value in the 
            // input 2D-array 
            int v1 = getSum(BIT, i, j); 
            int v2 = getSum(BIT, i, j - 1); 
            int v3 = getSum(BIT, i - 1, j - 1); 
            int v4 = getSum(BIT, i - 1, j); 
 
            // Assigning a value to a particular element 
            // of 2D BIT 
            updateBIT(BIT, i, j, aux[i][j] - 
                     (v1 - v2 - v4 + v3)); 
        } 
    } 
    return; 
} 
 
// A function to answer the queries 
static void answerQueries(Query q[], int m, int BIT[][]) 
{ 
    for (int i = 0; i < m; i++) 
    { 
        int x1 = q[i].x1 + 1; 
        int y1 = q[i].y1 + 1; 
        int x2 = q[i].x2 + 1; 
        int y2 = q[i].y2 + 1; 
 
        int ans = getSum(BIT, x2, y2) -
                  getSum(BIT, x2, y1 - 1) - 
                  getSum(BIT, x1 - 1, y2) +
                  getSum(BIT, x1 - 1, y1 - 1); 
 
        System.out.printf("Query(%d, %d, %d, %d) = %d\n", 
                q[i].x1, q[i].y1, q[i].x2, q[i].y2, ans); 
    } 
    return; 
} 
 
// Driver Code
public static void main(String[] args) 
{ 
    int mat[][] = { {1, 2, 3, 4}, 
                    {5, 3, 8, 1}, 
                    {4, 6, 7, 5}, 
                    {2, 4, 8, 9} }; 
 
    // Create a 2D Binary Indexed Tree 
    int [][]BIT = new int[N + 1][N + 1]; 
    construct2DBIT(mat, BIT); 
 
    /* Queries of the form - x1, y1, x2, y2 
    For example the query- {1, 1, 3, 2} means the sub-matrix- 
        y 
        /\ 
    3 | 1 2 3 4     Sub-matrix 
    2 | 5 3 8 1     {1,1,3,2} --.     3 8 1 
    1 | 4 6 7 5                                 6 7 5 
    0 | 2 4 8 9 
        | 
    --|------ 0 1 2 3 ---. x 
        | 
     
        Hence sum of the sub-matrix = 3+8+1+6+7+5 = 30 
    */
    Query q[] = {new Query(1, 1, 3, 2), 
                 new Query(2, 3, 3, 3), 
                 new Query(1, 1, 1, 1)}; 
    int m = q.length; 
 
    answerQueries(q, m, BIT); 
}
} 
 
// This code is contributed by 29AjayKumar

Python3

'''Python3  program to implement 2D Binary Indexed Tree 
   
2D BIT is basically a BIT where each element is another BIT. 
Updating by adding v on (x, y) means it's effect will be found 
throughout the rectangle [(x, y), (max_x, max_y)], 
and query for (x, y) gives you the result of the rectangle 
[(0, 0), (x, y)], assuming the total rectangle is 
[(0, 0), (max_x, max_y)]. So when you query and update on 
this BIT,you have to be careful about how many times you are 
subtracting a rectangle and adding it. Simple set union formula 
works here. 
   
So if you want to get the result of a specific rectangle 
[(x1, y1), (x2, y2)], the following steps are necessary: 
   
Query(x1,y1,x2,y2) = getSum(x2, y2)-getSum(x2, y1-1) - 
                    getSum(x1-1, y2)+getSum(x1-1, y1-1) 
   
Here 'Query(x1,y1,x2,y2)' means the sum of elements enclosed 
in the rectangle with bottom-left corner's co-ordinates 
(x1, y1) and top-right corner's co-ordinates - (x2, y2) 
   
Constraints -> x1<=x2 and y1<=y2 
   
    /\ 
y | 
    |     --------(x2,y2) 
    |     | | 
    |     | | 
    |     | | 
    |     --------- 
    | (x1,y1) 
    | 
    |___________________________ 
(0, 0)             x--> 
   
In this program we have assumed a square matrix. The 
program can be easily extended to a rectangular one. '''
 
N = 4 # N-.max_x and max_y 
 
# A structure to hold the queries 
class Query:
 
    def __init__(self, x1,y1,x2,y2):
     
        self.x1 = x1;
        self.y1 = y1;
        self.x2 = x2;
        self.y2 = y2;
 
 
# A function to update the 2D BIT 
def updateBIT(BIT,x,y,val):
     
    while x <= N:
     
        # This loop update all the 1D BIT inside the 
        # array of 1D BIT = BIT[x] 
        while y <= N:
            BIT[x][y] += val;
            y += (y & -y)
         
        x += (x & -x)
     
    return; 
 
 
# A function to get sum from (0, 0) to (x, y) 
def getSum(BIT,x,y):
 
    sum = 0; 
     
    while x > 0:
        # This loop sum through all the 1D BIT 
        # inside the array of 1D BIT = BIT[x] 
        while y > 0:
 
            sum += BIT[x][y]; 
            y -= y&-y
         
        x -= x&-x
     
    return sum; 
 
 
# A function to create an auxiliary matrix 
# from the given input matrix 
def constructAux(mat,aux):
    # Initialise Auxiliary array to 0 
    for  i in range(N + 1):
        for j in range(N + 1):
            aux[i][j] = 0
   
    # Construct the Auxiliary Matrix 
    for j in range(1, N + 1):
        for i in range(1, N + 1):
            aux[i][j] = mat[N - j][i - 1];
   
    return
 
 
# A function to construct a 2D BIT 
def construct2DBIT(mat,BIT):
    # Create an auxiliary matrix 
    aux = [None for i in range(N + 1)]
    for i in range(N + 1) : 
     
        aux[i]= [None for i in range(N + 1)]
     
    constructAux(mat, aux)
   
    # Initialise the BIT to 0 
    for i in range(1, N + 1): 
        for j in range(1, N + 1): 
            BIT[i][j] = 0; 
   
    for j in range(1, N + 1): 
     
        for i in range(1, N + 1): 
         
            # Creating a 2D-BIT using update function 
            # everytime we/ encounter a value in the 
            # input 2D-array 
            v1 = getSum(BIT, i, j); 
            v2 = getSum(BIT, i, j - 1); 
            v3 = getSum(BIT, i - 1, j - 1); 
            v4 = getSum(BIT, i - 1, j); 
   
            # Assigning a value to a particular element 
            # of 2D BIT 
            updateBIT(BIT, i, j, aux[i][j] -
                     (v1 - v2 - v4 + v3)); 
         
     
    return; 
 
 
# A function to answer the queries 
def answerQueries(q,m,BIT):
     
    for i in range(m):
      
        x1 = q[i].x1 + 1; 
        y1 = q[i].y1 + 1; 
        x2 = q[i].x2 + 1; 
        y2 = q[i].y2 + 1; 
   
        ans = getSum(BIT, x2, y2) - \
                  getSum(BIT, x2, y1 - 1) - \
                  getSum(BIT, x1 - 1, y2) + \
                  getSum(BIT, x1 - 1, y1 - 1); 
   
        print("Query (", q[i].x1, ", ", q[i].y1, ", ", q[i].x2, ", " , q[i].y2, ") = " ,ans, sep = "") 
     
    return; 
 
 
# Driver Code
mat= [[1, 2, 3, 4], 
                    [5, 3, 8, 1], 
                    [4, 6, 7, 5], 
                    [2, 4, 8, 9]]; 
   
# Create a 2D Binary Indexed Tree 
BIT = [None for i in range(N + 1)]
for i in range(N + 1):
 
    BIT[i]= [None for i in range(N + 1)]
    for j in range(N + 1):
            BIT[i][j]=0
         
     
construct2DBIT(mat, BIT); 
   
''' Queries of the form - x1, y1, x2, y2 
    For example the query- {1, 1, 3, 2} means the sub-matrix- 
        y 
        /\ 
    3 | 1 2 3 4     Sub-matrix 
    2 | 5 3 8 1     {1,1,3,2} --.     3 8 1 
    1 | 4 6 7 5                                 6 7 5 
    0 | 2 4 8 9 
        | 
    --|------ 0 1 2 3 ---. x 
        | 
       
        Hence sum of the sub-matrix = 3+8+1+6+7+5 = 30 
     
    '''
q = [Query(1, 1, 3, 2), Query(2, 3, 3, 3), Query(1, 1, 1, 1)]; 
m = len(q)
   
answerQueries(q, m, BIT); 
 
# This code is contributed by phasing17

C#

/* C# program to implement 2D Binary Indexed Tree 
 
2D BIT is basically a BIT where each element is another BIT. 
Updating by.Adding v on (x, y) means it's effect will be found 
throughout the rectangle [(x, y), (max_x, max_y)], 
and query for (x, y) gives you the result of the rectangle 
[(0, 0), (x, y)], assuming the total rectangle is 
[(0, 0), (max_x, max_y)]. So when you query and update on 
this BIT,you have to be careful about how many times you are 
subtracting a rectangle and.Adding it. Simple set union formula 
works here. 
 
So if you want to get the result of a specific rectangle 
[(x1, y1), (x2, y2)], the following steps are necessary: 
 
Query(x1,y1,x2,y2) = getSum(x2, y2)-getSum(x2, y1-1) - 
                    getSum(x1-1, y2)+getSum(x1-1, y1-1) 
 
Here 'Query(x1,y1,x2,y2)' means the sum of elements enclosed 
in the rectangle with bottom-left corner's co-ordinates 
(x1, y1) and top-right corner's co-ordinates - (x2, y2) 
 
Constraints -> x1<=x2 and y1<=y2 
 
    /\ 
y | 
    |     --------(x2,y2) 
    |     | | 
    |     | | 
    |     | | 
    |     --------- 
    | (x1,y1) 
    | 
    |___________________________ 
(0, 0)             x--> 
 
In this program we have assumed a square matrix. The 
program can be easily extended to a rectangular one. */
using System;
 
class GFG
{ 
static readonly int N = 4; // N-.max_x and max_y 
 
// A structure to hold the queries 
public class Query 
{ 
    public int x1, y1; // x and y co-ordinates of bottom left 
    public int x2, y2; // x and y co-ordinates of top right 
 
        public Query(int x1, int y1, int x2, int y2)
        {
            this.x1 = x1;
            this.y1 = y1;
            this.x2 = x2;
            this.y2 = y2;
        }
         
}; 
 
// A function to update the 2D BIT 
static void updateBIT(int [,]BIT, int x,
                    int y, int val) 
{ 
    for (; x <= N; x += (x & -x)) 
    { 
        // This loop update all the 1D BIT inside the 
        // array of 1D BIT = BIT[x] 
        for (; y <= N; y += (y & -y)) 
            BIT[x,y] += val; 
    } 
    return; 
} 
 
// A function to get sum from (0, 0) to (x, y) 
static int getSum(int [,]BIT, int x, int y) 
{ 
    int sum = 0; 
 
    for(; x > 0; x -= x&-x) 
    { 
        // This loop sum through all the 1D BIT 
        // inside the array of 1D BIT = BIT[x] 
        for(; y > 0; y -= y&-y) 
        { 
            sum += BIT[x, y]; 
        } 
    } 
    return sum; 
} 
 
// A function to create an auxiliary matrix 
// from the given input matrix 
static void constructAux(int [,]mat, int [,]aux) 
{ 
    // Initialise Auxiliary array to 0 
    for (int i = 0; i <= N; i++) 
        for (int j = 0; j <= N; j++) 
            aux[i, j] = 0; 
 
    // Construct the Auxiliary Matrix 
    for (int j = 1; j <= N; j++) 
        for (int i = 1; i <= N; i++) 
            aux[i, j] = mat[N - j, i - 1]; 
 
    return; 
} 
 
// A function to construct a 2D BIT 
static void construct2DBIT(int [,]mat,
                        int [,]BIT) 
{ 
    // Create an auxiliary matrix 
    int [,]aux = new int[N + 1, N + 1]; 
    constructAux(mat, aux); 
 
    // Initialise the BIT to 0 
    for (int i = 1; i <= N; i++) 
        for (int j = 1; j <= N; j++) 
            BIT[i, j] = 0; 
 
    for (int j = 1; j <= N; j++) 
    { 
        for (int i = 1; i <= N; i++) 
        { 
            // Creating a 2D-BIT using update function 
            // everytime we/ encounter a value in the 
            // input 2D-array 
            int v1 = getSum(BIT, i, j); 
            int v2 = getSum(BIT, i, j - 1); 
            int v3 = getSum(BIT, i - 1, j - 1); 
            int v4 = getSum(BIT, i - 1, j); 
 
            // Assigning a value to a particular element 
            // of 2D BIT 
            updateBIT(BIT, i, j, aux[i,j] - 
                    (v1 - v2 - v4 + v3)); 
        } 
    } 
    return; 
} 
 
// A function to answer the queries 
static void answerQueries(Query []q, int m, int [,]BIT) 
{ 
    for (int i = 0; i < m; i++) 
    { 
        int x1 = q[i].x1 + 1; 
        int y1 = q[i].y1 + 1; 
        int x2 = q[i].x2 + 1; 
        int y2 = q[i].y2 + 1; 
 
        int ans = getSum(BIT, x2, y2) -
                getSum(BIT, x2, y1 - 1) - 
                getSum(BIT, x1 - 1, y2) +
                getSum(BIT, x1 - 1, y1 - 1); 
 
        Console.Write("Query({0}, {1}, {2}, {3}) = {4}\n", 
                q[i].x1, q[i].y1, q[i].x2, q[i].y2, ans); 
    } 
    return; 
} 
 
// Driver Code
public static void Main(String[] args) 
{ 
    int [,]mat = { {1, 2, 3, 4}, 
                    {5, 3, 8, 1}, 
                    {4, 6, 7, 5}, 
                    {2, 4, 8, 9} }; 
 
    // Create a 2D Binary Indexed Tree 
    int [,]BIT = new int[N + 1,N + 1]; 
    construct2DBIT(mat, BIT); 
 
    /* Queries of the form - x1, y1, x2, y2 
    For example the query- {1, 1, 3, 2} means the sub-matrix- 
        y 
        /\ 
    3 | 1 2 3 4     Sub-matrix 
    2 | 5 3 8 1     {1,1,3,2} --.     3 8 1 
    1 | 4 6 7 5                                 6 7 5 
    0 | 2 4 8 9 
        | 
    --|------ 0 1 2 3 ---. x 
        | 
     
        Hence sum of the sub-matrix = 3+8+1+6+7+5 = 30 
    */
    Query []q = {new Query(1, 1, 3, 2), 
                new Query(2, 3, 3, 3), 
                new Query(1, 1, 1, 1)}; 
    int m = q.Length; 
 
    answerQueries(q, m, BIT); 
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
/* Javascript program to implement 2D Binary Indexed Tree 
   
2D BIT is basically a BIT where each element is another BIT. 
Updating by adding v on (x, y) means it's effect will be found 
throughout the rectangle [(x, y), (max_x, max_y)], 
and query for (x, y) gives you the result of the rectangle 
[(0, 0), (x, y)], assuming the total rectangle is 
[(0, 0), (max_x, max_y)]. So when you query and update on 
this BIT,you have to be careful about how many times you are 
subtracting a rectangle and adding it. Simple set union formula 
works here. 
   
So if you want to get the result of a specific rectangle 
[(x1, y1), (x2, y2)], the following steps are necessary: 
   
Query(x1,y1,x2,y2) = getSum(x2, y2)-getSum(x2, y1-1) - 
                    getSum(x1-1, y2)+getSum(x1-1, y1-1) 
   
Here 'Query(x1,y1,x2,y2)' means the sum of elements enclosed 
in the rectangle with bottom-left corner's co-ordinates 
(x1, y1) and top-right corner's co-ordinates - (x2, y2) 
   
Constraints -> x1<=x2 and y1<=y2 
   
    /\ 
y | 
    |     --------(x2,y2) 
    |     | | 
    |     | | 
    |     | | 
    |     --------- 
    | (x1,y1) 
    | 
    |___________________________ 
(0, 0)             x--> 
   
In this program we have assumed a square matrix. The 
program can be easily extended to a rectangular one. */
 
let N = 4; // N-.max_x and max_y 
 
// A structure to hold the queries 
class Query 
{
    constructor(x1,y1,x2,y2)
    {
        this.x1 = x1;
            this.y1 = y1;
            this.x2 = x2;
            this.y2 = y2;
    }
}
 
// A function to update the 2D BIT 
function updateBIT(BIT,x,y,val)
{
    for (; x <= N; x += (x & -x)) 
    { 
        // This loop update all the 1D BIT inside the 
        // array of 1D BIT = BIT[x] 
        for (; y <= N; y += (y & -y)) 
            BIT[x][y] += val; 
    } 
    return; 
}
 
// A function to get sum from (0, 0) to (x, y) 
function getSum(BIT,x,y)
{
    let sum = 0; 
   
    for(; x > 0; x -= x&-x) 
    { 
        // This loop sum through all the 1D BIT 
        // inside the array of 1D BIT = BIT[x] 
        for(; y > 0; y -= y&-y) 
        { 
            sum += BIT[x][y]; 
        } 
    } 
    return sum; 
}
 
// A function to create an auxiliary matrix 
// from the given input matrix 
function constructAux(mat,aux)
{
    // Initialise Auxiliary array to 0 
    for (let i = 0; i <= N; i++) 
        for (let j = 0; j <= N; j++) 
            aux[i][j] = 0; 
   
    // Construct the Auxiliary Matrix 
    for (let j = 1; j <= N; j++) 
        for (let i = 1; i <= N; i++) 
            aux[i][j] = mat[N - j][i - 1]; 
   
    return; 
}
 
// A function to construct a 2D BIT 
function construct2DBIT(mat,BIT)
{
    // Create an auxiliary matrix 
    let aux = new Array(N + 1);
    for(let i=0;i<(N+1);i++)
    {
        aux[i]=new Array(N+1);
    }
    constructAux(mat, aux); 
   
    // Initialise the BIT to 0 
    for (let i = 1; i <= N; i++) 
        for (let j = 1; j <= N; j++) 
            BIT[i][j] = 0; 
   
    for (let j = 1; j <= N; j++) 
    { 
        for (let i = 1; i <= N; i++) 
        { 
            // Creating a 2D-BIT using update function 
            // everytime we/ encounter a value in the 
            // input 2D-array 
            let v1 = getSum(BIT, i, j); 
            let v2 = getSum(BIT, i, j - 1); 
            let v3 = getSum(BIT, i - 1, j - 1); 
            let v4 = getSum(BIT, i - 1, j); 
   
            // Assigning a value to a particular element 
            // of 2D BIT 
            updateBIT(BIT, i, j, aux[i][j] - 
                     (v1 - v2 - v4 + v3)); 
        } 
    } 
    return; 
}
 
// A function to answer the queries 
function answerQueries(q,m,BIT)
{
    for (let i = 0; i < m; i++) 
    { 
        let x1 = q[i].x1 + 1; 
        let y1 = q[i].y1 + 1; 
        let x2 = q[i].x2 + 1; 
           let y2 = q[i].y2 + 1; 
   
        let ans = getSum(BIT, x2, y2) -
                  getSum(BIT, x2, y1 - 1) - 
                  getSum(BIT, x1 - 1, y2) +
                  getSum(BIT, x1 - 1, y1 - 1); 
   
        document.write("Query ("+q[i].x1+", " +q[i].y1+", " +q[i].x2+", " +q[i].y2+") = " +ans+"<br>"); 
    } 
    return; 
}
 
// Driver Code
let mat= [[1, 2, 3, 4], 
                    [5, 3, 8, 1], 
                    [4, 6, 7, 5], 
                    [2, 4, 8, 9]]; 
   
    // Create a 2D Binary Indexed Tree 
    let BIT = new Array(N + 1);
    for(let i=0;i<(N+1);i++)
    {
        BIT[i]=new Array(N+1);
        for(let j=0;j<(N+1);j++)
        {
            BIT[i][j]=0;
        }
    }
    construct2DBIT(mat, BIT); 
   
    /* Queries of the form - x1, y1, x2, y2 
    For example the query- {1, 1, 3, 2} means the sub-matrix- 
        y 
        /\ 
    3 | 1 2 3 4     Sub-matrix 
    2 | 5 3 8 1     {1,1,3,2} --.     3 8 1 
    1 | 4 6 7 5                                 6 7 5 
    0 | 2 4 8 9 
        | 
    --|------ 0 1 2 3 ---. x 
        | 
       
        Hence sum of the sub-matrix = 3+8+1+6+7+5 = 30 
    */
    let q = [new Query(1, 1, 3, 2), 
                 new Query(2, 3, 3, 3), 
                 new Query(1, 1, 1, 1)]; 
    let m = q.length; 
   
    answerQueries(q, m, BIT); 
 
 
// This code is contributed by rag2127
</script>

Output

Query(1, 1, 3, 2) = 30
Query(2, 3, 3, 3) = 7
Query(1, 1, 1, 1) = 6

Time Complexity:

Both updateBIT(x, y, val) function and getSum(x, y) function takes O(log(N)*log(M)) time.
Building the 2D BIT takes O(NM log(N)*log(M)).
Since in each of the queries we are calling getSum(x, y) function so answering all the Q queries takes O(Q*log(N)*log(M)) time.
Hence the overall time complexity of the program is O((NM+Q)*log(N)*log(M)) where,
N = maximum X co-ordinate of the whole matrix.
M = maximum Y co-ordinate of the whole matrix.
Q = Number of queries.

Auxiliary Space: O(NM) to store the BIT and the auxiliary array

Suggest improvement

Range sum query using Sparse Table

Parent and Child Classes Having Same Data Member in Java

Share your thoughts in the comments

Two Dimensional Binary Indexed Tree or Fenwick Tree

Can we answer sub-matrix sum queries efficiently using Binary Indexed Tree ?

C++

Java

Python3

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?