Two Dimensional Fenwick Tree

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];
            }
        }
        return totalsum;
    }

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];
            }
        }
        return totalsum;
    }

    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;
}

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

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

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.