Dada una array de tamaño M x N, hay un gran número de consultas para encontrar sumas de subarrays. Las entradas a las consultas son los índices superior izquierdo e inferior derecho de la subarray cuya suma es averiguar.
Cómo preprocesar la array para que las consultas de suma de subarray se puedan realizar en tiempo O(1).
Ejemplo :
tli : Row number of top left of query submatrix
tlj : Column number of top left of query submatrix
rbi : Row number of bottom right of query submatrix
rbj : Column number of bottom right of query submatrix
Input: mat[M][N] = {{1, 2, 3, 4, 6},
{5, 3, 8, 1, 2},
{4, 6, 7, 5, 5},
{2, 4, 8, 9, 4} };
Query1: tli = 0, tlj = 0, rbi = 1, rbj = 1
Query2: tli = 2, tlj = 2, rbi = 3, rbj = 4
Query3: tli = 1, tlj = 2, rbi = 3, rbj = 3;
Output:
Query1: 11 // Sum between (0, 0) and (1, 1)
Query2: 38 // Sum between (2, 2) and (3, 4)
Query3: 38 // Sum between (1, 2) and (3, 3)
Le recomendamos encarecidamente que minimice su navegador y que pruebe esto usted mismo primero.
La idea es crear primero una array auxiliar aux[M][N] tal que aux[i][j] almacene la suma de elementos en la subarray desde (0,0) hasta (i,j). Una vez que se construye aux[][], podemos calcular la suma de la subarray entre (tli, tlj) y (rbi, rbj) en tiempo O(1). Necesitamos considerar aux[rbi][rbj] y restar todos los elementos innecesarios. A continuación se muestra la expresión completa para calcular la suma de la subarray en tiempo O(1).
C++
// C++ program to compute submatrix query sum in O(1)
// time
#include<iostream>
using namespace std;
#define M 4
#define N 5
// Function to preprocess input mat[M][N]. This function
// mainly fills aux[M][N] such that aux[i][j] stores sum
// of elements from (0,0) to (i,j)
int preProcess(int mat[M][N], int aux[M][N])
{
// Copy first row of mat[][] to aux[][]
for (int i=0; i<N; i++)
aux[0][i] = mat[0][i];
// Do column wise sum
for (int i=1; i<M; i++)
for (int j=0; j<N; j++)
aux[i][j] = mat[i][j] + aux[i-1][j];
// Do row wise sum
for (int i=0; i<M; i++)
for (int j=1; j<N; j++)
aux[i][j] += aux[i][j-1];
}
// A O(1) time function to compute sum of submatrix
// between (tli, tlj) and (rbi, rbj) using aux[][]
// which is built by the preprocess function
int sumQuery(int aux[M][N], int tli, int tlj, int rbi,
int rbj)
{
// result is now sum of elements between (0, 0) and
// (rbi, rbj)
int res = aux[rbi][rbj];
// Remove elements between (0, 0) and (tli-1, rbj)
if (tli > 0)
res = res - aux[tli-1][rbj];
// Remove elements between (0, 0) and (rbi, tlj-1)
if (tlj > 0)
res = res - aux[rbi][tlj-1];
// Add aux[tli-1][tlj-1] as elements between (0, 0)
// and (tli-1, tlj-1) are subtracted twice
if (tli > 0 && tlj > 0)
res = res + aux[tli-1][tlj-1];
return res;
}
// Driver program
int main()
{
int mat[M][N] = {{1, 2, 3, 4, 6},
{5, 3, 8, 1, 2},
{4, 6, 7, 5, 5},
{2, 4, 8, 9, 4} };
int aux[M][N];
preProcess(mat, aux);
int tli = 2, tlj = 2, rbi = 3, rbj = 4;
cout << "\nQuery1: " << sumQuery(aux, tli, tlj, rbi, rbj);
tli = 0, tlj = 0, rbi = 1, rbj = 1;
cout << "\nQuery2: " << sumQuery(aux, tli, tlj, rbi, rbj);
tli = 1, tlj = 2, rbi = 3, rbj = 3;
cout << "\nQuery3: " << sumQuery(aux, tli, tlj, rbi, rbj);
return 0;
}
Java
// Java program to compute submatrix query
// sum in O(1) time
class GFG {
static final int M = 4;
static final int N = 5;
// Function to preprocess input mat[M][N].
// This function mainly fills aux[M][N]
// such that aux[i][j] stores sum of
// elements from (0,0) to (i,j)
static int preProcess(int mat[][], int aux[][])
{
// Copy first row of mat[][] to aux[][]
for (int i = 0; i < N; i++)
aux[0][i] = mat[0][i];
// Do column wise sum
for (int i = 1; i < M; i++)
for (int j = 0; j < N; j++)
aux[i][j] = mat[i][j] +
aux[i-1][j];
// Do row wise sum
for (int i = 0; i < M; i++)
for (int j = 1; j < N; j++)
aux[i][j] += aux[i][j-1];
return 0;
}
// A O(1) time function to compute sum
// of submatrix between (tli, tlj) and
// (rbi, rbj) using aux[][] which is
// built by the preprocess function
static int sumQuery(int aux[][], int tli,
int tlj, int rbi, int rbj)
{
// result is now sum of elements
// between (0, 0) and (rbi, rbj)
int res = aux[rbi][rbj];
// Remove elements between (0, 0)
// and (tli-1, rbj)
if (tli > 0)
res = res - aux[tli-1][rbj];
// Remove elements between (0, 0)
// and (rbi, tlj-1)
if (tlj > 0)
res = res - aux[rbi][tlj-1];
// Add aux[tli-1][tlj-1] as elements
// between (0, 0) and (tli-1, tlj-1)
// are subtracted twice
if (tli > 0 && tlj > 0)
res = res + aux[tli-1][tlj-1];
return res;
}
// Driver code
public static void main (String[] args)
{
int mat[][] = {{1, 2, 3, 4, 6},
{5, 3, 8, 1, 2},
{4, 6, 7, 5, 5},
{2, 4, 8, 9, 4}};
int aux[][] = new int[M][N];
preProcess(mat, aux);
int tli = 2, tlj = 2, rbi = 3, rbj = 4;
System.out.print("\nQuery1: "
+ sumQuery(aux, tli, tlj, rbi, rbj));
tli = 0; tlj = 0; rbi = 1; rbj = 1;
System.out.print("\nQuery2: "
+ sumQuery(aux, tli, tlj, rbi, rbj));
tli = 1; tlj = 2; rbi = 3; rbj = 3;
System.out.print("\nQuery3: "
+ sumQuery(aux, tli, tlj, rbi, rbj));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python 3 program to compute submatrix
# query sum in O(1) time
M = 4
N = 5
# Function to preprocess input mat[M][N].
# This function mainly fills aux[M][N]
# such that aux[i][j] stores sum
# of elements from (0,0) to (i,j)
def preProcess(mat, aux):
# Copy first row of mat[][] to aux[][]
for i in range(0, N, 1):
aux[0][i] = mat[0][i]
# Do column wise sum
for i in range(1, M, 1):
for j in range(0, N, 1):
aux[i][j] = mat[i][j] + aux[i - 1][j]
# Do row wise sum
for i in range(0, M, 1):
for j in range(1, N, 1):
aux[i][j] += aux[i][j - 1]
# A O(1) time function to compute sum of submatrix
# between (tli, tlj) and (rbi, rbj) using aux[][]
# which is built by the preprocess function
def sumQuery(aux, tli, tlj, rbi, rbj):
# result is now sum of elements
# between (0, 0) and (rbi, rbj)
res = aux[rbi][rbj]
# Remove elements between (0, 0)
# and (tli-1, rbj)
if (tli > 0):
res = res - aux[tli - 1][rbj]
# Remove elements between (0, 0)
# and (rbi, tlj-1)
if (tlj > 0):
res = res - aux[rbi][tlj - 1]
# Add aux[tli-1][tlj-1] as elements
# between (0, 0) and (tli-1, tlj-1)
# are subtracted twice
if (tli > 0 and tlj > 0):
res = res + aux[tli - 1][tlj - 1]
return res
# Driver Code
if __name__ == '__main__':
mat = [[1, 2, 3, 4, 6],
[5, 3, 8, 1, 2],
[4, 6, 7, 5, 5],
[2, 4, 8, 9, 4]]
aux = [[0 for i in range(N)]
for j in range(M)]
preProcess(mat, aux)
tli = 2
tlj = 2
rbi = 3
rbj = 4
print("Query1:", sumQuery(aux, tli, tlj, rbi, rbj))
tli = 0
tlj = 0
rbi = 1
rbj = 1
print("Query2:", sumQuery(aux, tli, tlj, rbi, rbj))
tli = 1
tlj = 2
rbi = 3
rbj = 3
print("Query3:", sumQuery(aux, tli, tlj, rbi, rbj))
# This code is contributed by
# Shashank_Sharma
C#
// C# program to compute submatrix
// query sum in O(1) time
using System;
class GFG
{
static int M = 4;
static int N = 5;
// Function to preprocess input mat[M][N].
// This function mainly fills aux[M][N]
// such that aux[i][j] stores sum of
// elements from (0,0) to (i,j)
static int preProcess(int [,]mat, int [,]aux)
{
// Copy first row of mat[][] to aux[][]
for (int i = 0; i < N; i++)
aux[0,i] = mat[0,i];
// Do column wise sum
for (int i = 1; i < M; i++)
for (int j = 0; j < N; j++)
aux[i,j] = mat[i,j] + aux[i-1,j];
// Do row wise sum
for (int i = 0; i < M; i++)
for (int j = 1; j < N; j++)
aux[i,j] += aux[i,j-1];
return 0;
}
// A O(1) time function to compute sum
// of submatrix between (tli, tlj) and
// (rbi, rbj) using aux[][] which is
// built by the preprocess function
static int sumQuery(int [,]aux, int tli,
int tlj, int rbi, int rbj)
{
// result is now sum of elements
// between (0, 0) and (rbi, rbj)
int res = aux[rbi,rbj];
// Remove elements between (0, 0)
// and (tli-1, rbj)
if (tli > 0)
res = res - aux[tli-1,rbj];
// Remove elements between (0, 0)
// and (rbi, tlj-1)
if (tlj > 0)
res = res - aux[rbi,tlj-1];
// Add aux[tli-1][tlj-1] as elements
// between (0, 0) and (tli-1, tlj-1)
// are subtracted twice
if (tli > 0 && tlj > 0)
res = res + aux[tli-1,tlj-1];
return res;
}
// Driver code
public static void Main ()
{
int [,]mat = {{1, 2, 3, 4, 6},
{5, 3, 8, 1, 2},
{4, 6, 7, 5, 5},
{2, 4, 8, 9, 4}};
int [,]aux = new int[M,N];
preProcess(mat, aux);
int tli = 2, tlj = 2, rbi = 3, rbj = 4;
Console.Write("\nQuery1: " +
sumQuery(aux, tli, tlj, rbi, rbj));
tli = 0; tlj = 0; rbi = 1; rbj = 1;
Console.Write("\nQuery2: " +
sumQuery(aux, tli, tlj, rbi, rbj));
tli = 1; tlj = 2; rbi = 3; rbj = 3;
Console.Write("\nQuery3: " +
sumQuery(aux, tli, tlj, rbi, rbj));
}
}
// This code is contributed by Sam007.
PHP
<?php
// PHP program to compute submatrix
// query sum in O(1) time
// Function to preprocess input mat[M][N].
// This function mainly fills aux[M][N]
// such that aux[i][j] stores sum
// of elements from (0,0) to (i,j)
function preProcess(&$mat, &$aux)
{
$M = 4;
$N = 5;
// Copy first row of mat[][] to aux[][]
for ($i = 0; $i < $N; $i++)
$aux[0][$i] = $mat[0][$i];
// Do column wise sum
for ($i = 1; $i < $M; $i++)
for ($j = 0; $j < $N; $j++)
$aux[$i][$j] = $mat[$i][$j] +
$aux[$i - 1][$j];
// Do row wise sum
for ($i = 0; $i < $M; $i++)
for ($j = 1; $j < $N; $j++)
$aux[$i][$j] += $aux[$i][$j - 1];
}
// A O(1) time function to compute sum of
// submatrix between (tli, tlj) and
// (rbi, rbj) using aux[][] which is built
// by the preprocess function
function sumQuery(&$aux, $tli, $tlj, $rbi,$rbj)
{
// result is now sum of elements
// between (0, 0) and (rbi, rbj)
$res = $aux[$rbi][$rbj];
// Remove elements between (0, 0)
// and (tli-1, rbj)
if ($tli > 0)
$res = $res - $aux[$tli - 1][$rbj];
// Remove elements between (0, 0)
// and (rbi, tlj-1)
if ($tlj > 0)
$res = $res - $aux[$rbi][$tlj - 1];
// Add aux[tli-1][tlj-1] as elements between (0, 0)
// and (tli-1, tlj-1) are subtracted twice
if ($tli > 0 && $tlj > 0)
$res = $res + $aux[$tli - 1][$tlj - 1];
return $res;
}
// Driver Code
$mat = array(array(1, 2, 3, 4, 6),
array(5, 3, 8, 1, 2),
array(4, 6, 7, 5, 5),
array(2, 4, 8, 9, 4));
preProcess($mat, $aux);
$tli = 2;
$tlj = 2;
$rbi = 3;
$rbj = 4;
echo ("Query1: ");
echo(sumQuery($aux, $tli, $tlj, $rbi, $rbj));
$tli = 0;
$tlj = 0;
$rbi = 1;
$rbj = 1;
echo ("\nQuery2: ");
echo(sumQuery($aux, $tli, $tlj, $rbi, $rbj));
$tli = 1;
$tlj = 2;
$rbi = 3;
$rbj = 3;
echo ("\nQuery3: ");
echo(sumQuery($aux, $tli, $tlj, $rbi, $rbj));
// This code is contributed by Shivi_Aggarwal
?>
Javascript
<script>
// Javascript program to compute submatrix query
// sum in O(1) time
var M = 4;
var N = 5;
// Function to preprocess input mat[M][N].
// This function mainly fills aux[M][N]
// such that aux[i][j] stores sum of
// elements from (0,0) to (i,j)
function preProcess(mat, aux)
{
// Copy first row of mat[][] to aux[][]
for (var i = 0; i < N; i++)
aux[0,i] = mat[0,i];
// Do column wise sum
for (var i = 1; i < M; i++)
for (var j = 0; j < N; j++)
aux[i][j] = mat[i][j] +
aux[i-1][j];
// Do row wise sum
for (var i = 0; i < M; i++)
for (var j = 1; j < N; j++)
aux[i][j] += aux[i][j-1];
return 0;
}
// A O(1) time function to compute sum
// of submatrix between (tli, tlj) and
// (rbi, rbj) using aux[][] which is
// built by the preprocess function
function sumQuery( aux, tli, tlj, rbi, rbj)
{
// result is now sum of elements
// between (0, 0) and (rbi, rbj)
var res = aux[rbi][rbj];
// Remove elements between (0, 0)
// and (tli-1, rbj)
if (tli > 0)
res = res - aux[tli-1][rbj];
// Remove elements between (0, 0)
// and (rbi, tlj-1)
if (tlj > 0)
res = res - aux[rbi][tlj-1];
// Add aux[tli-1][tlj-1] as elements
// between (0, 0) and (tli-1, tlj-1)
// are subtracted twice
if (tli > 0 && tlj > 0)
res = res + aux[tli-1][tlj-1];
return res;
}
// Driver code
var mat= [[1, 2, 3, 4, 6],
[5, 3, 8, 1, 2],
[4, 6, 7, 5, 5],
[2, 4, 8, 9, 4]];
var aux = new Array(M,N);
preProcess(mat, aux);
var tli = 2, tlj = 2, rbi = 3, rbj = 4;
document.write("\nQuery1: "
+ sumQuery(aux, tli, tlj, rbi, rbj)+"<br>");
tli = 0; tlj = 0; rbi = 1; rbj = 1;
document.write("\nQuery2: "
+ sumQuery(aux, tli, tlj, rbi, rbj)+"<br>");
tli = 1; tlj = 2; rbi = 3; rbj = 3;
document.write("\nQuery3: "
+ sumQuery(aux, tli, tlj, rbi, rbj));
}
}
// This code is contributed by shivanisinghss2110
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA