Dada una array (o array 2D) a[][] de enteros, encuentre la array de suma de prefijos para ella. Deje que la array de suma de prefijos sea psa [] []. El valor de psa[i][j] contiene la suma de todos los valores que están encima oa la izquierda.
Requisito previo: Suma de prefijo – 1D
Una solución simple es encontrar psa[i][j] recorriendo y sumando valores de a[0][0] a a[i][j]. La complejidad temporal de esta solución es O(R * C * R * C).
Una solución eficiente es usar valores calculados previamente para calcular psa[i][j]. A diferencia de la suma de prefijos de array 1D, esto es complicado, aquí si simplemente agregamos psa[i][j-1] y psa[i-1][j], obtenemos la suma de elementos de a[0][0] a a [i-1][j-1] dos veces, entonces restamos psa[i-1][j-1].
Ejemplo :
psa[3][3] = psa[2][3] + psa[3][2] -
psa[2][2] + a[3][3]
= 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]
A continuación se muestra la implementación del enfoque anterior.
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 = 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];
}
// 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 << "\n";
}
}
// 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 ("\n");
}
}
// 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)
?>
Javascript
<script>
// Javascript program to find prefix sum of 2D array
// calculating new array
function prefixSum2D(a)
{
let R = a.length;
let C = a[0].length;
let psa = new Array(R);
for(let i = 0; i < R; i++)
{
psa[i] = new Array(C);
for(let j = 0; j < C; j++)
psa[i][j] = 0;
}
psa[0][0] = a[0][0];
// Filling first row and first column
for (let i = 1; i < C; i++)
psa[0][i] = psa[0][i - 1] + a[0][i];
for (let 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 (let i = 1; i < R; i++)
for (let 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 (let i = 0; i < R; i++) {
for (let j = 0; j < C; j++)
document.write(psa[i][j] + " ");
document.write("<br>");
}
}
// driver code
let 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 avanitrachhadiya2155
</script>
Producción :
1 2 3 4 5 2 4 6 8 10 3 6 9 12 15 4 8 12 16 20
Complejidad de Tiempo : O(R*C)
Espacio Auxiliar : O(R*C)