Tutorialspoint.dev

Prefix Sum of Matrix (Or 2D Array)

Given a matrix (or 2D array) a[][] of integers, find prefix sum matrix for it. Let prefix sum matrix be psa[][]. The value of psa[i][j] contains sum of all values which are above it or on left of it.

prefix-sum-matrix



Prerequisite: Prefix Sum – 1D

A simple solution is to find psa[i][j] by traversing and adding values from a[0][0] to a[i][j]. Time complexity o this solution is O(R * C * R * C).

An efficient solution is to use previously computed values to compute psa[i][j]. Unlike 1D array prefix sum, this is tricky, here if we simply add psa[i][j-1] and psa[i-1][j], we get sum of elements from a[0][0] to a[i-1][j-1] twice, so we subtract psa[i-1][j-1].

Example :

psa[3][3] = psa[2][3] + psa[3][2] -
            psa[2][2] + a[2][2]
          = 6 + 6 - 4 + 1
          = 9
The general formula: 
psa[i][j] = psa[i-1][j] + psa[i][j-1] - 
            psa[i-1][j-1] + a[i][j]

Corner Cases (First row and first column)
If i = 0 and j = 0
   psa[i][j] = a[i][j]
If i = 0 and j > 0
   psa[i][j] = psa[i][j-1] + a[i][j]
If i > 0 and j = 0
   psa[i][j] = psa[i-1][j] + a[i][j]

Below is the implementation of the above approach

C++

// C++ Program to find prefix sum of 2d array
#include <bits/stdc++.h>
using namespace std;
  
#define R 4
#define C 5
  
// calculating new array
void prefixSum2D(int a[][C])
{
    int psa[R][C];
    psa[0][0] = a[0][0];
  
    // Filling first row and first column
    for (int i = 1; i < C; i++)
        psa[0][i] = psa[0][i - 1] + a[0][i];
    for (int i = 0; i < R; i++)
        psa[i][0] = psa[i - 1][0] + a[i][0];
  
    // updating the values in the cells
    // as per the general formula
    for (int i = 1; i < R; i++) {
        for (int j = 1; j < C; j++)
  
            // values in the cells of new
            // array are updated
            psa[i][j] = psa[i - 1][j] + psa[i][j - 1]
                        - psa[i - 1][j - 1] + a[i][j];
    }
  
    // displaying the values of the new array
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++)
            cout << psa[i][j] << " ";
        cout << " ";
    }
}
  
// driver code
int main()
{
    int a[R][C] = { { 1, 1, 1, 1, 1 },
                    { 1, 1, 1, 1, 1 },
                    { 1, 1, 1, 1, 1 },
                    { 1, 1, 1, 1, 1 } };
  
    prefixSum2D(a);
  
    return 0;
}

Java

// Java program to find prefix sum of 2D array
import java.util.*;
  
class GFG {
  
    // calculating new array
    public static void prefixSum2D(int a[][])
    {
        int R = a.length;
        int C = a[0].length;
  
        int psa[][] = new int[R][C];
  
        psa[0][0] = a[0][0];
  
        // Filling first row and first column
        for (int i = 1; i < C; i++)
            psa[0][i] = psa[0][i - 1] + a[0][i];
        for (int i = 1; i < R; i++)
            psa[i][0] = psa[i - 1][0] + a[i][0];
  
        // updating the values in the
        // cells as per the general formula.
        for (int i = 1; i < R; i++)
            for (int j = 1; j < C; j++)
  
                // values in the cells of new array
                // are updated
                psa[i][j] = psa[i - 1][j] + psa[i][j - 1]
                            - psa[i - 1][j - 1] + a[i][j];
  
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++)
                System.out.print(psa[i][j] + " ");
            System.out.println();
        }
    }
  
    // driver code
    public static void main(String[] args)
    {
        int a[][] = { { 1, 1, 1, 1, 1 },
                      { 1, 1, 1, 1, 1 },
                      { 1, 1, 1, 1, 1 },
                      { 1, 1, 1, 1, 1 } };
        prefixSum2D(a);
    }
}

Python3

# Python Program to find 
# prefix sum of 2d array
R = 4
C = 5
  
# calculating new array
def prefixSum2D(a) :
    global C, R
    psa = [[0 for x in range(C)] 
              for y in range(R)] 
    psa[0][0] = a[0][0]
  
    # Filling first row 
    # and first column
    for i in range(1, C) :
        psa[0][i] = (psa[0][i - 1] + 
                       a[0][i])
    for i in range(0, R) :
        psa[i][0] = (psa[i - 1][0] + 
                       a[i][0])
  
    # updating the values in 
    # the cells as per the 
    # general formula
    for i in range(1, R) :
        for j in range(1, C) :
  
            # values in the cells of 
            # new array are updated
            psa[i][j] = (psa[i - 1][j] + 
                         psa[i][j - 1] - 
                         psa[i - 1][j - 1] + 
                           a[i][j])
  
    # displaying the values
    # of the new array
    for i in range(0, R) :
        for j in range(0, C) :
            print (psa[i][j], 
                   end = " ")
        print ()
  
# Driver Code
a = [[ 1, 1, 1, 1, 1 ],
     [ 1, 1, 1, 1, 1 ],
     [ 1, 1, 1, 1, 1 ],
     [ 1, 1, 1, 1, 1 ]]
  
prefixSum2D(a)
  
# This code is contributed by 
# Manish Shaw(manishshaw1)

C#

// C# program to find prefix
// sum of 2D array
using System;
  
class GFG 
{
  
    // calculating new array
    static void prefixSum2D(int [,]a)
    {
        int R = a.GetLength(0);
        int C = a.GetLength(1);
  
        int [,]psa = new int[R, C];
  
        psa[0, 0] = a[0, 0];
  
        // Filling first row
        // and first column
        for (int i = 1; i < C; i++)
            psa[0, i] = psa[0, i - 1] + 
                               a[0, i];
        for (int i = 1; i < R; i++)
            psa[i, 0] = psa[i - 1, 0] + 
                               a[i, 0];
   
        // updating the values in the
        // cells as per the general formula.
        for (int i = 1; i < R; i++)
            for (int j = 1; j < C; j++)
  
                // values in the cells of 
                // new array are updated
                psa[i, j] = psa[i - 1, j] + 
                            psa[i, j - 1] - 
                            psa[i - 1, j - 1] + 
                            a[i, j];
  
        for (int i = 0; i < R; i++) 
        {
            for (int j = 0; j < C; j++)
                Console.Write(psa[i, j] + " ");
            Console.WriteLine();
        }
    }
  
    // Driver Code
    static void Main()
    {
        int [,]a = new int[,]{{1, 1, 1, 1, 1},
                              {1, 1, 1, 1, 1},
                              {1, 1, 1, 1, 1},
                              {1, 1, 1, 1, 1}};
        prefixSum2D(a);
    }
}
  
// This code is contributed by manishshaw1

PHP

<?php
// PHP Program to find 
// prefix sum of 2d array
$R = 4;
$C = 5;
  
// calculating new array
function prefixSum2D($a)
{
    global $C, $R;
    $psa = array();
    $psa[0][0] = $a[0][0];
  
    // Filling first row 
    // and first column
    for ($i = 1; $i < $C; $i++)
        $psa[0][$i] = $psa[0][$i - 1] + 
                             $a[0][$i];
    for ($i = 0; $i < $R; $i++)
        $psa[$i][0] = $psa[$i - 1][0] + 
                             $a[$i][0];
  
    // updating the values in 
    // the cells as per the 
    // general formula
    for ($i = 1; $i < $R; $i++)
    {
        for ($j = 1; $j < $C; $j++)
  
            // values in the cells of 
            // new array are updated
            $psa[$i][$j] = $psa[$i - 1][$j] + 
                           $psa[$i][$j - 1] - 
                           $psa[$i - 1][$j - 1] + 
                           $a[$i][$j];
    }
  
    // displaying the values
    // of the new array
    for ($i = 0; $i < $R; $i++) 
    {
        for ($j = 0; $j < $C; $j++)
            echo ($psa[$i][$j]. " ");
        echo (" ");
    }
}
  
// Driver Code
$a = array(array( 1, 1, 1, 1, 1 ),
           array( 1, 1, 1, 1, 1 ),
           array( 1, 1, 1, 1, 1 ),
           array( 1, 1, 1, 1, 1 ));
  
prefixSum2D($a);
  
// This code is contributed by 
// Manish Shaw(manishshaw1)
?>

Output :

1 2 3 4 5 
2 4 6 8 10 
3 6 9 12 15 
4 8 12 16 20


Time Complexity :
O(R*C)
Auxiliary Space : O(R*C)



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter