can someone provide me the algorithm of 2-d binary indexed tree?

Question

I searched on internet but couldn't find a good one. I got some help from geeksforgeeks.org but can't understand the construction part where we are subtracting v1-v2-v2-v4+v3 from aux[i][j] while updating the BIT array. Just let me know why we are subtracting here.

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

Answer 1

There is a good explanation of 2d binary indexed trees on topcoder.

To understand the aux[i][j]-(v1-v2-v4+v3) note that:

1. getSum(BIT,i,j) returns the sum of all elements in a rectangle with top-left at the origin, and bottom-right at coordinates i,j.
2. therefore getSum(BIT, i, j)-getSum(BIT, i, j-1) is the sum of all elements in row j across to column i
3. therefore getSum(BIT, i-1, j)-getSum(BIT, i-1, j-1) is the sum of all elements in row j across to column i-1
4. therefore v1-v2-v4+v3 is value of entry at position i,j

The update code works by adding a value at a position. In this code they want to set the value to a particular choice in aux[i][j] so the way to do that is to add the difference between the target value and the current value.

(Having said that, this code updates each value in turn, so you should find that v1-v2-v4+v3 is always equal to zero because every value starts cleared)