Prefix Sum Of Matrix (OR 2D Array) In C++

In this tutorial, we shall learn to solve the prefix sum of a matrix (or 2D array) problem in C++. It is an application of competitive programming. A prefix matrix is such a matrix whose every element is the sum of all values above it or on the left of it.

The general approach to this problem is to traverse the whole 2D array from arr[0][0] to arr[i][j] and add the values in a step-wise manner. But it would cost us the time complexity of O(R*C*R*C) which is equivalent to O(n^4) which is huge obviously (R and C are rows and columns respectively).
So we would do this job in much lesser time complexity of O(R*C) i.e. of O(n^2). We would increase our efficiency by using the previously computed values to compute psa (our prefix sum array).

The Efficient Algorithm And Its Special Cases

So, here the tricky part comes in, the special cases.

The general case:
psa[i][j] = psa[i-1][j] + psa[i][j-1] - psa[i-1][j-1] + a[i][j]
Else:
For i = j = 0, psa[i][j] = arr[i][j]
For i = 0 and j > 0, psa[i][j] = psa[i][j-1] + arr[i][j]
For i > 0 and j = 0, psa[i][j] = psa[i-1][j] + arr[i][j]

We take input by the user of a 3 * 3 matrix. We also print that matrix once and then call the function prefixsumarray() which takes the parameter as a 2D array and then prints the computed prefix array. The thing here that I want to point out is that while we pass a multidimensional array then we have to take care that declaration of ‘array’ as multidimensional array must have bounds for all dimensions except the first, i.e. the compiler just ignores the first bound. For example, declaring using arr[][3] is completely fine.

#include <bits/stdc++.h>
typedef long long ll; // macro for long long
void prefixsumarray(ll arr[][3]);
using namespace std;
int main()
{
    ll arr[3][3];
    cout << "Enter the 3 by 3 matrix (2D array) " << endl;
    for (ll i = 0; i < 3; i++)
        for (ll j = 0; j < 3; j++)
            cin >> arr[i][j];
    for (ll i = 0; i < 3; i++)
    {
        cout << endl;
        for (ll j = 0; j < 3; j++)
            cout << arr[i][j] << " ";
    }
    cout << endl
         << endl;
    prefixsumarray(arr);

    return 0;
}
void prefixsumarray(ll arr[][3]) // declaration of 'array' as multidimensional array must have bounds for all dimensions except the first
{
    ll psa[3][3];
    psa[0][0] = arr[0][0]; // For i=0 and j=0

    for (int i = 1; i < 3; i++)
        psa[0][i] = psa[0][i - 1] + arr[0][i]; // For i = 0 and j > 0
    for (int i = 1; i < 3; i++)
        psa[i][0] = psa[i - 1][0] + arr[i][0]; // For i > 0 and j = 0

    for (int i = 1; i < 3; i++) // general formula for element at (i,j) position
    {
        for (int j = 1; j < 3; j++)

            psa[i][j] = psa[i - 1][j] + psa[i][j - 1] - psa[i - 1][j - 1] + arr[i][j];
    }

    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
            cout << psa[i][j] << " ";
        cout << "\n";
    }
}

For the input:

1 2 3
4 5 6
7 8 9

The output is:

Enter the 3 by 3 matrix (2D array)
1 2 3
4 5 6
7 8 9

1 2 3
4 5 6
7 8 9

1 3 6
5 12 21
12 27 45

You may also like to learn:

Leave a Reply

Your email address will not be published. Required fields are marked *