1.
Introduction
2.
Problem Statement
2.1.
Example 1
2.1.1.
Input
2.1.2.
Output
2.1.3.
Explanation
3.
Approach
3.1.
Code:
3.2.
Output:
4.

4.1.
Time Complexity
4.2.
Space Complexity
5.
FAQs
6.
Key Takeaways
Last Updated: Mar 27, 2024

# Two Dimensional Fenwick Tree

Apoorv
1 upvote

## Introduction

Two Dimensional Fenwick Tree is widely used in industry and has a lot of applications. One of the most common applications of the Two Dimensional Fenwick Tree is to find the sub-matrix queries efficiently. So let's understand the given problem statement in a better way. To understand the 2D Fenwick tree, you must first understand the Fenwick tree. The 2D Fenwick tree, like the 1D Fenwick tree, requires the operation to be invertible.

## Problem Statement

We are given Two Dimensional matrices we have to Perform some queries on the given matrix.

Query1:Find the Sum of all the elements in a  sub-matrix according to a given query. In the query, we are given top left corner coordinates and bottom right corner coordinates, querysum(x1, y1, x2, y2).

Query 2:We have to add the given value in the query at a given index in the query of the matrix like this (x1, y1, value).

### Example 1

#### Input

Input matrix[][] is

[ 0  2  5  4  1 ]

[ 4  8  2  3  7 ]

[ 6  3  4  6  2 ]

[ 7  3  1  8  3 ]

[ 1  5  7  9  4 ]

Size = 5 * 5

Queries:

Queries are based on one based indexing like (0,0) coordinate is considered as (1,1)

Query 1: querysum(2, 2, 4, 4)

Query 2: queryupdate(3, 3, 4)

Query 3: querysum(2, 2, 4, 4)

#### Output

Input Matrix is

0 2 5 4 1

4 8 2 3 7

6 3 4 6 2

7 3 1 8 3

1 5 7 9 4

Sum of submatrix ((2, 2), (4, 4)) is 38

After changing 4 at coordinate (3, 3) to 8, matrix is

0 2 5 4 1

4 8 2 3 7

6 3 8 6 2

7 3 1 8 3

1 5 7 9 4

Sum of submatrix ((2, 2), (4, 4)) is 42

#### Explanation

[ 0  2  5  4  1 ]

[ 4  8  2  3  7 ]

[ 6  3  4  6  2 ]

[ 7  3  1  8  3 ]

[ 1  5  7  9  4 ]

The submatrix formed by coordinates (2, 2), (2, 4), (4, 2), and (4, 4) is shown below, having the Sum of elements equal to 38.

[ 8  2  3 ]

[ 3  4  6 ]

[ 3  1  8 ]

After performing the second query the new matrix will be

[ 0  2  5  4  1 ] [ 0  2  5  4  1 ]

[ 4  8  2  3  7 ] [ 4  8  2  3  7 ]

[ 6  3  4+4  6  2 ]   =   [ 6  3  8  6  2 ]

[ 7  3  1  8  3 ] [ 7  3  1  8  3 ]

[ 1  5  7  9  4 ] [ 1  5  7  9  4 ]

For the third query, the submatrix formed by coordinates (2, 2), (2, 4), (4, 2), and (4, 4) is shown below, having the Sum of elements equal to 42.

[ 0  2  5  4  1 ]

[ 4  8  2  3  7 ]

[ 6  3  8  6  2 ]

[ 7  3  1  8  3 ]

[ 1  5  7  9  4 ]

[ 8  2  3 ]

[ 3  8  6 ]

[ 3  1  8 ]

## Approach

Since the Fenwick tree stores the prefix sum, the 1D Fenwick tree works by processing query(x, y) as query(1, y) - query(1, x - 1). Two Dimensional Fenwick Tree operates on a matrix, so the query is processed differently, but the requirement is still the same, i.e., the operation must be invertible. Using the principle of inclusion-exclusion we can find the sum with the given formula.

sum((x1, y1), (x2, y2)) = sum((0, 0), (x2, y2)) - sum((0, 0), (x1 - 1, y2))  - sum((0, 0), (x2, y1 - 1)) + sum((0, 0), (x1 - 1, y1 - 1))

Since the Sum of this submatrix sum((0, 0), (x1 - 1, y1 - 1))  was subtracted two times hence we also need to add this one time.

Let's understand the same with an example :

[ 0  2  5  4  1 ]

[ 4  8  2  3  7 ]

[ 6  3  4  6  2 ]

[ 7  3  1  8  3 ]

[ 1  5  7  9  4 ]

If we have to calculate the sum from sum(1,1,3,3)

= sum(0,0,3,3)-sum(0,0,0,3)-sum(0,0,3,0)+sum(0,0,0,0)

= 64-17-11+0

= 38

Just like the Fenwick tree, the Least-significant-bit operation is used in Two Dimensional Fenwick Tree:

``````int leastSignificantBit(int i){
return i & (-i);
}``````

D Fenwick tree is implemented same as the matrix of the same size as target matrix. For a row x col matrix, Two Dimensional Fenwick Tree is also stored as row x col matrix. Two Dimensional Fenwick Tree is just a 2D visualization of a Fenwick tree.

Inputmatrix[][] is the row x col matrix upon which the Two Dimensional Fenwick Tree is built.

twodft[][] is the row x col matrix used to store Two Dimensional Fenwick Tree.

Finding the Sum of a submatrix can be done the same as done in linear fenwick tree, but in a two-dimensional Fenwick tree, we have to iterate in both directions row-wise and column-wise to get the Sum of a submatrix starting from (0,0) to (X, Y)

``````    int querySum(int x, int y){
int totalsum = 0;
for(int i = x; i > 0; i = i - leastSignificantBit(i)){
for(int j = y; j > 0; j = j - leastSignificantBit(j)){
totalsum = totalsum + twodft[i][j];
}
}
}``````

Similarly, for updation, we have to update all the elements after the given coordinates, which is updated in the input matrix. There will be no changes for the coordinates less than the given coordinates in the query. If we have updated (3,3), there is no need to change the value in the submatrix of the Fenwick tree with coordinates less than (3,3). We have to do updation on only those coordinates greater than (3,3). While updating, we will update on the given index, then we will move to the next coordinate having the next set bit compared with the given coordinate.

For example, if we are currently on the index (row, col)  = (3,3) and want to update the value at index (3,3) Then first we will update the index at (3,3) Then we start iterating in a row, and next index on which we have to update will be obtained by adding the least significant bit to the current index value.

So adding the least significant bit in 3 will be 000….11 + 00000……1 = 0…..100, which is 4 so we will update the index (3,4)

Now updating 4 with the next least significant bit will go out of range that is out of 6th index so we will reinetialize the col index to 3 and then staring moving in colum direction.

Given below is the diagrammatic presentation of how the updation will work.

``````    void queryUpdate(int x, int y, int value){

// also update matrix[x][y] if needed.
for(int x_ = x; x_ < twodft.size(); x_ = x_ + leastSignificantBit(x_)){
for(int y_ = y; y_ < twodft[0].size(); y_ = y_ + leastSignificantBit(y_)){
twodft[x_][y_] += value;
}
}
}``````

### Code:

``````// Two Dimensional Fenwick Tree Implementation for sub-matrix sum problem
#include <bits/stdc++.h>
using namespace std;

class FenwickTree{
private:

// Matrix to store the Two Dimensional Fenwick Tree
vector<vector<int>> twodft;

public:

// Function to get least significant bit
int leastSignificantBit(int x){
return x & (-x);
}

int querySum(int x, int y){
int totalsum = 0;
for(int i = x; i > 0; i = i - leastSignificantBit(i)){
for(int j = y; j > 0; j = j - leastSignificantBit(j)){
totalsum = totalsum + twodft[i][j];
}
}
}

int querySum(int x1, int y1, int x2, int y2){

// Principle of inclusion and exclusion
return (querySum(x2, y2) - querySum(x1 - 1, y2) - querySum(x2, y1 - 1) +   querySum(x1 - 1, y1 - 1));
}

void queryUpdate(int x, int y, int value){

// also update matrix[x][y] if needed.
for(int x_ = x; x_ < twodft.size(); x_ = x_ + leastSignificantBit(x_)){
for(int y_ = y; y_ < twodft[0].size(); y_ = y_ + leastSignificantBit(y_)){
twodft[x_][y_] += value;
}
}
}

FenwickTree(vector<vector<int>> inputMatrix){

int row = inputMatrix.size();
// The inputMatrix should not be empty.
int col = inputMatrix[0].size();

// Initialize matrix ft
twodft.assign(col + 1, vector<int> (row + 1, 0));

for(int i = 0; i < col; ++i){
for(int j = 0; j < row; ++j)
queryUpdate(i + 1, j + 1, inputMatrix[i][j]);
}
}
};

int main(){
//Input Matrix
vector<vector<int>> inputMatrix = {vector<int>({0,2,5,4,1}),
vector<int>({4,8,2,3,7}),
vector<int>({6,3,4,6,2}),
vector<int>({7,3,1,8,3}),
vector<int>({1,5,7,9,4})};

// Making object of Two Dimensional Fenwick Tree
FenwickTree twodft(inputMatrix);

// Printing the Input
cout << "Input Matrix is"<<endl;
for(int i = 0; i < 5; ++i){
for(int j = 0; j < 5; ++j)
cout << inputMatrix[i][j] << ' ';
cout <<endl;
}

cout <<endl;

// Query type 1
cout << "Sum of submatrix ((2, 2), (4, 4)) is ";
cout<<twodft.querySum(2, 2, 4, 4) <<endl;

// Query type 2
cout << "After changing 4 at coordinate (3, 3) to 8, matrix is"<<endl;

// Updating the value to 4 at new index
inputMatrix[2 - 1][2 - 1] += 4;
twodft.queryUpdate(3, 3, 4);

// Printing the new matrix
for(int i = 0; i < 5; ++i){
for(int j = 0; j < 5; ++j)
cout << inputMatrix[i][j] << ' ';
cout <<endl;
}
cout <<endl;

// Query type 1
cout << "Sum of submatrix ((2, 2), (4, 4)) is ";
cout<<twodft.querySum(2, 2, 4, 4) <<endl;

return 0;
}``````

### Time Complexity

O(log2(row * col))+O(row * col * log2(row * col))

The time complexity to do sub-matrix queries in a Two Dimensional Fenwick Tree is O(log2(row * col)), where row * col is the size of the input matrix. Update and finding sum query will cost O(log2(row * col)) time. To find the Sum of a submatrix, we must iterate both in a row and column direction while iterating; We are not going in all the elements. We only iterate to the last set bit from the given coordinate, costing only logarithmic time. But building a 2d Fenwick tree will cost O(row * col*log2(row * col)) this time because we are iterating on both rows and columns and to update each element in the matrix will cost O(log2(row * col)) time so the total time complexity will be O(log2(row * col))+O(row * col * log2(row * col)).

### Space Complexity

O(row * col)

The space complexity for sub-matrix queries in a Two Dimensional Fenwick Tree is O(row * col), where row*col is the input matrix size. We are creating another extra matrix of the same size as the input matrix to store the element in the form of Two Dimensional Fenwick Tree.

Check out this problem - Count Inversions

## FAQs

1. What are Fenwick trees?
A Fenwick tree, also known as a binary indexed tree, is a data structure that can quickly update items in a table of numbers and calculate prefix sums.

2. Where are Fenwick trees used?
A Fenwick tree helps in the computation of prefix sums. Prefix sums are frequently used in a variety of other algorithms, as well as in a number of competitive programming contests. , For example, They're utilized to implement the arithmetic coding algorithm.

3. How is the Fenwick tree is making the solution more effective?
Fenwick tree uses the concept of bits. Least-significant-bit operation is used in the Fenwick tree array to compute the results of the prefix array which can be calculated in logarithmic time.

## Key Takeaways

In this blog, we discussed the solution for doing submatrix queries using Two Dimensional Fenwick Tree; the article also focused on the time and space complexity of the solution.

If you want to learn more about the Two Dimensional Fenwick Tree and want to practice some quality questions which require you to excel your preparation a notch higher, then you can visit our Guided Path for Two Dimensional Fenwick Tree on Coding Ninjas Studio.To be more confident in data structures and algorithms, try out our DS and Algo Course. Until then, All the best for your future endeavors, and Keep Coding.

Live masterclass