Dada una array 2D mat[][] de tamaño N*M y Q consultas de la forma {x1, y1, x2, y2, K} . Para cada consulta, la tarea es agregar el valor K a la subarray desde la celda (x1, y1) a (x2, y2) . Imprime la array después de todas las consultas realizadas.
Ejemplos:
Entrada: N = 3, M = 4, mat[][] = {{1, 0, 1, 2}, {0, 2, 4, 1}, {1, 2, 1, 0}}, Q = 1, Consultas[][] = {{0, 0, 1, 1, 2}}
Salida:
3 2 1 2
2 4 4 1
1 2 1 0
Explicación:
solo hay una consulta, es decir, actualizar la subarray desde el tapete de la celda [0][0] a mat[1][1] en incrementos de 2, la array se convierte en:
3 2 1 2
2 4 4 1
1 2 1 0Entrada: N = 2, M = 3, mat[][] = {{3, 2, 1}, {2, 4, 4}}, Q = 1, Consultas[][] = { {0, 1, 1, 2, -1}, {0, 0, 1, 1, 5}}
Salida:
8 6 0
7 8 3
Explicación:
para la consulta 1, es decir, actualizar la subarray de celda mat[0][1] a mat [1][2] por incremento de (-1), la array se convierte en:
3 1 0
2 3 3
Para la consulta 2, es decir, actualizar la subarray de la celda mat[0][0] a mat[2][2] por incremento de 5, la array se convierte en:
8 6 0
7 8 3
Enfoque ingenuo : el enfoque más simple es iterar sobre la subarray y agregar K a todos los elementos desde mat[x1][y1] hasta mat[x2][y2] para cada consulta. Imprime la array después de las operaciones anteriores.
Complejidad temporal: O(N*M*Q)
Espacio auxiliar: O(1)
Enfoque eficiente : la idea es usar una array auxiliar para realizar las operaciones de actualización en las esquinas de las celdas de la subarray y luego encontrar la suma del prefijo de la array para obtener la array resultante. A continuación se muestran los pasos:
- Inicialice todos los elementos de la array auxiliar, digamos aux[][] a 0 .
- Para cada consulta {x1, y1, x2, y2, K} actualice la array auxiliar como:
- auxiliar[x1][y1] += K
- si(x2 + 1 < N) entonces aux[x2 + 1][y1] -= K
- si(x2 + 1 < N && y2 + 1 < N) entonces aux[x2 + 1][y2 + 1] += K
- si(y2 + 1 < N) entonces aux[x1][y2 + 1] -= K
- Encuentre la suma de prefijos de cada fila de la array auxiliar.
- Encuentre la suma de prefijos de cada columna de la array auxiliar.
- Ahora, actualice la array auxiliar como la suma de los elementos en cada celda respectiva de la array auxiliar y dada.
- Imprime la array auxiliar después de todas las operaciones anteriores.
A continuación se muestra la ilustración de cómo se crea y actualiza la array auxiliar para query[][] = {{0, 0, 1, 1, 2}, {0, 1, 2, 3, -1}} :
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
#define N 3
#define M 4
// Query data type
struct query {
int x1, x2, y1, y2, K;
};
// Function to update the given query
void updateQuery(int from_x, int from_y,
int to_x, int to_y,
int k, int aux[][M])
{
// Update top cell
aux[from_x][from_y] += k;
// Update bottom left cell
if (to_x + 1 < N)
aux[to_x + 1][from_y] -= k;
// Update bottom right cell
if (to_x + 1 < N && to_y + 1 < M)
aux[to_x + 1][to_y + 1] += k;
// Update top right cell
if (to_y + 1 < M)
aux[from_x][to_y + 1] -= k;
}
// Function that updates the matrix
// mat[][] by adding elements of aux[][]
void updateMatrix(int mat[][M], int aux[][M])
{
// Compute the prefix sum of all columns
for (int i = 0; i < N; i++) {
for (int j = 1; j < M; j++) {
aux[i][j] += aux[i][j - 1];
}
}
// Compute the prefix sum of all rows
for (int i = 0; i < M; i++) {
for (int j = 1; j < N; j++) {
aux[j][i] += aux[j - 1][i];
}
}
// Get the final matrix by adding
// mat and aux matrix at each cell
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
mat[i][j] += aux[i][j];
}
}
}
// Function that prints matrix mat[]
void printMatrix(int mat[][M])
{
// Traverse each row
for (int i = 0; i < N; i++) {
// Traverse each columns
for (int j = 0; j < M; j++) {
cout << mat[i][j] << " ";
}
cout << "\n";
}
}
// Function that performs each query in
// the given matrix and print the updated
// matrix after each operation performed
void matrixQuery(int mat[][M], int Q,
query q[])
{
// Initialize all elements to 0
int aux[N][M] = {};
// Update auxiliary matrix
// by traversing each query
for (int i = 0; i < Q; i++) {
// Update Query
updateQuery(q[i].x1, q[i].x2,
q[i].y1, q[i].y2,
q[i].K, aux);
}
// Compute the final answer
updateMatrix(mat, aux);
// Print the updated matrix
printMatrix(mat);
}
// Driver Code
int main()
{
// Given Matrix
int mat[N][M] = { { 1, 0, 1, 2 },
{ 0, 2, 4, 1 },
{ 1, 2, 1, 0 } };
int Q = 1;
// Given Queries
query q[] = { { 0, 0, 1, 1, 2 } };
// Function Call
matrixQuery(mat, Q, q);
return 0;
}
Java
// Java program for the above approach
class GFG{
static final int N = 3;
static final int M = 4;
// Query data type
static class query
{
int x1, x2, y1, y2, K;
public query(int x1, int x2,
int y1, int y2, int k)
{
this.x1 = x1;
this.x2 = x2;
this.y1 = y1;
this.y2 = y2;
K = k;
}
};
// Function to update the given query
static void updateQuery(int from_x, int from_y,
int to_x, int to_y,
int k, int aux[][])
{
// Update top cell
aux[from_x][from_y] += k;
// Update bottom left cell
if (to_x + 1 < N)
aux[to_x + 1][from_y] -= k;
// Update bottom right cell
if (to_x + 1 < N && to_y + 1 < M)
aux[to_x + 1][to_y + 1] += k;
// Update top right cell
if (to_y + 1 < M)
aux[from_x][to_y + 1] -= k;
}
// Function that updates the matrix
// mat[][] by adding elements of aux[][]
static void updateMatrix(int mat[][],
int aux[][])
{
// Compute the prefix sum of all columns
for (int i = 0; i < N; i++)
{
for (int j = 1; j < M; j++)
{
aux[i][j] += aux[i][j - 1];
}
}
// Compute the prefix sum of all rows
for (int i = 0; i < M; i++)
{
for (int j = 1; j < N; j++)
{
aux[j][i] += aux[j - 1][i];
}
}
// Get the final matrix by adding
// mat and aux matrix at each cell
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
mat[i][j] += aux[i][j];
}
}
}
// Function that prints matrix mat[]
static void printMatrix(int mat[][])
{
// Traverse each row
for (int i = 0; i < N; i++)
{
// Traverse each columns
for (int j = 0; j < M; j++)
{
System.out.print(mat[i][j] + " ");
}
System.out.print("\n");
}
}
// Function that performs each query in
// the given matrix and print the updated
// matrix after each operation performed
static void matrixQuery(int mat[][],
int Q, query q[])
{
// Initialize all elements to 0
int [][]aux = new int[N][M];
// Update auxiliary matrix
// by traversing each query
for (int i = 0; i < Q; i++)
{
// Update Query
updateQuery(q[i].x1, q[i].x2,
q[i].y1, q[i].y2,
q[i].K, aux);
}
// Compute the final answer
updateMatrix(mat, aux);
// Print the updated matrix
printMatrix(mat);
}
// Driver Code
public static void main(String[] args)
{
// Given Matrix
int mat[][] = {{1, 0, 1, 2},
{0, 2, 4, 1},
{1, 2, 1, 0}};
int Q = 1;
// Given Queries
query q[] = {new query(0, 0, 1, 1, 2 )};
// Function Call
matrixQuery(mat, Q, q);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach # Query data type # Function to update the given query def updateQuery(from_x, from_y, to_x, to_y, k, aux): # Update top cell aux[from_x][from_y] += k # Update bottom left cell if (to_x + 1 < 3): aux[to_x + 1][from_y] -= k # Update bottom right cell if (to_x + 1 < 3 and to_y + 1 < 4): aux[to_x + 1][to_y + 1] += k # Update top right cell if (to_y + 1 < 4): aux[from_x][to_y + 1] -= k # return aux # Function that updates the matrix # mat[][] by adding elements of aux[][] def updatematrix(mat, aux): # Compute the prefix sum of all columns for i in range(3): for j in range(1, 4): aux[i][j] += aux[i][j - 1] # Compute the prefix sum of all rows for i in range(4): for j in range(1, 3): aux[j][i] += aux[j - 1][i] # Get the final matrix by adding # mat and aux matrix at each cell for i in range(3): for j in range(4): mat[i][j] += aux[i][j] # return mat # Function that prints matrix mat[] def printmatrix(mat): # Traverse each row for i in range(3): # Traverse each columns for j in range(4): print(mat[i][j], end = " ") print() # Function that performs each query in # the given matrix and print the updated # matrix after each operation performed def matrixQuery(mat, Q, q): # Initialize all elements to 0 aux = [[ 0 for i in range(4)] for i in range(3)] # Update auxiliary matrix # by traversing each query for i in range(Q): # Update Query updateQuery(q[i][0], q[i][1], q[i][2], q[i][3], q[i][4], aux) # Compute the final answer updatematrix(mat, aux) # Print the updated matrix printmatrix(mat) # Driver Code if __name__ == '__main__': # Given 4atrix mat = [ [ 1, 0, 1, 2 ], [ 0, 2, 4, 1 ], [ 1, 2, 1, 0 ] ] Q = 1 # Given Queries q = [ [0, 0, 1, 1, 2 ] ] # Function Call matrixQuery(mat, Q, q) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
static readonly int N = 3;
static readonly int M = 4;
// Query data type
class query
{
public int x1, x2, y1, y2, K;
public query(int x1, int x2,
int y1, int y2,
int k)
{
this.x1 = x1;
this.x2 = x2;
this.y1 = y1;
this.y2 = y2;
K = k;
}
};
// Function to update the given query
static void updateQuery(int from_x, int from_y,
int to_x, int to_y,
int k, int [,]aux)
{
// Update top cell
aux[from_x, from_y] += k;
// Update bottom left cell
if (to_x + 1 < N)
aux[to_x + 1, from_y] -= k;
// Update bottom right cell
if (to_x + 1 < N && to_y + 1 < M)
aux[to_x + 1, to_y + 1] += k;
// Update top right cell
if (to_y + 1 < M)
aux[from_x, to_y + 1] -= k;
}
// Function that updates the matrix
// [,]mat by adding elements of aux[,]
static void updateMatrix(int [,]mat,
int [,]aux)
{
// Compute the prefix sum of all columns
for(int i = 0; i < N; i++)
{
for(int j = 1; j < M; j++)
{
aux[i, j] += aux[i, j - 1];
}
}
// Compute the prefix sum of all rows
for(int i = 0; i < M; i++)
{
for(int j = 1; j < N; j++)
{
aux[j, i] += aux[j - 1, i];
}
}
// Get the readonly matrix by adding
// mat and aux matrix at each cell
for(int i = 0; i < N; i++)
{
for(int j = 0; j < M; j++)
{
mat[i, j] += aux[i, j];
}
}
}
// Function that prints matrix []mat
static void printMatrix(int [,]mat)
{
// Traverse each row
for(int i = 0; i < N; i++)
{
// Traverse each columns
for(int j = 0; j < M; j++)
{
Console.Write(mat[i, j] + " ");
}
Console.Write("\n");
}
}
// Function that performs each query in
// the given matrix and print the updated
// matrix after each operation performed
static void matrixQuery(int [,]mat,
int Q, query []q)
{
// Initialize all elements to 0
int [,]aux = new int[N, M];
// Update auxiliary matrix
// by traversing each query
for(int i = 0; i < Q; i++)
{
// Update Query
updateQuery(q[i].x1, q[i].x2,
q[i].y1, q[i].y2,
q[i].K, aux);
}
// Compute the readonly answer
updateMatrix(mat, aux);
// Print the updated matrix
printMatrix(mat);
}
// Driver Code
public static void Main(String[] args)
{
// Given Matrix
int [,]mat = { { 1, 0, 1, 2 },
{ 0, 2, 4, 1 },
{ 1, 2, 1, 0 } };
int Q = 1;
// Given Queries
query []q = {new query( 0, 0, 1, 1, 2 )};
// Function call
matrixQuery(mat, Q, q);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for the above approach
let N = 3;
let M = 4;
// Query data type
class query
{
constructor(x1,x2,y1,y2,k)
{
this.x1 = x1;
this.x2 = x2;
this.y1 = y1;
this.y2 = y2;
this.K = k;
}
}
// Function to update the given query
function updateQuery(from_x,from_y,to_x,to_y,k,aux)
{
// Update top cell
aux[from_x][from_y] += k;
// Update bottom left cell
if (to_x + 1 < N)
aux[to_x + 1][from_y] -= k;
// Update bottom right cell
if (to_x + 1 < N && to_y + 1 < M)
aux[to_x + 1][to_y + 1] += k;
// Update top right cell
if (to_y + 1 < M)
aux[from_x][to_y + 1] -= k;
}
// Function that updates the matrix
// mat[][] by adding elements of aux[][]
function updateMatrix(mat,aux)
{
// Compute the prefix sum of all columns
for (let i = 0; i < N; i++)
{
for (let j = 1; j < M; j++)
{
aux[i][j] += aux[i][j - 1];
}
}
// Compute the prefix sum of all rows
for (let i = 0; i < M; i++)
{
for (let j = 1; j < N; j++)
{
aux[j][i] += aux[j - 1][i];
}
}
// Get the final matrix by adding
// mat and aux matrix at each cell
for (let i = 0; i < N; i++)
{
for (let j = 0; j < M; j++)
{
mat[i][j] += aux[i][j];
}
}
}
// Function that prints matrix mat[]
function printMatrix(mat)
{
// Traverse each row
for (let i = 0; i < N; i++)
{
// Traverse each columns
for (let j = 0; j < M; j++)
{
document.write(mat[i][j] + " ");
}
document.write("<br>");
}
}
// Function that performs each query in
// the given matrix and print the updated
// matrix after each operation performed
function matrixQuery(mat,Q,q)
{
// Initialize all elements to 0
let aux = new Array(N);
for(let i=0;i<N;i++)
{
aux[i]=new Array(M);
for(let j=0;j<M;j++)
{
aux[i][j]=0;
}
}
// Update auxiliary matrix
// by traversing each query
for (let i = 0; i < Q; i++)
{
// Update Query
updateQuery(q[i].x1, q[i].x2,
q[i].y1, q[i].y2,
q[i].K, aux);
}
// Compute the final answer
updateMatrix(mat, aux);
// Print the updated matrix
printMatrix(mat);
}
// Driver Code
// Given Matrix
let mat = [[1, 0, 1, 2],
[0, 2, 4, 1],
[1, 2, 1, 0]];
let Q = 1;
// Given Queries
let q = [new query(0, 0, 1, 1, 2 )];
// Function Call
matrixQuery(mat, Q, q);
// This code is contributed by unknown2108
</script>
Producción:
3 2 1 2 2 4 4 1 1 2 1 0
Complejidad temporal: O(Q + N*M)
Espacio auxiliar: O(N*M)
Publicación traducida automáticamente
Artículo escrito por se_prashant y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA