Imprimir array después de aplicar operaciones de incremento en M rangos

Dada una array 2-D mat[][] de tamaño N * N , inicialmente todos los elementos de la array son 0 . Se deben realizar varias consultas (rango M) en la array, donde cada consulta consta de cuatro números enteros X1 , Y1 , X2 e Y2 , la tarea es agregar 1 a todas las celdas entre mat[X1][Y1] y mat [X2][Y2] (incluidos ambos) e imprima el contenido de la array actualizada al final.
Ejemplos: 
 

Entrada: N = 2, q[][] = { { 0, 0, 1, 1 }, { 0, 0, 0, 1 } } 
Salida: 
2 2 
1 1 
Después de la primera consulta: mat[][] = { {1, 1}, {1, 1} } 
Después de la segunda consulta: mat[][] = { {2, 2}, {1, 1} }
Entrada: N = 5, q[][] = { { 0 , 0, 1, 2 }, { 1, 2, 3, 4 }, { 1, 4, 3, 4 } } 
Salida: 
1 1 1 1 1 
1 1 2 1 2 
2 2 2 2 2 
2 2 2 2 2 
0 0 0 0 0 
 

Enfoque: para cada consulta (X1, Y1) representa la celda superior izquierda de la subarray y (X2, Y2) representa la celda inferior derecha de la subarray. Para cada celda superior izquierda, agregue 1 al elemento superior izquierdo y reste 1 del elemento al lado de la celda inferior derecha (si corresponde). 
Luego mantenga una suma continua de todos los elementos de la array original (ahora modificada) y en cada adición, la suma actual es el elemento (actualizado) en la posición actual.
A continuación se muestra la implementación del enfoque anterior:
 

// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to update and print the
// matrix after performing queries
void updateMatrix(int n, int q[3][4])
{
    int i, j;
    int mat[n][n];
    for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
    mat[i][j] = 0;
    for (i = 0; i < 3; i++)
    {
        int X1 = q[i][0];
        int Y1 = q[i][1];
        int X2 = q[i][2];
        int Y2 = q[i][3];
 
        // Add 1 to the first element of
        // the sub-matrix
        mat[X1][Y1]++;
 
        // If there is an element after the
        // last element of the sub-matrix
        // then decrement it by 1
        if (Y2 + 1 < n)
            mat[X2][Y2 + 1]--;
        else if (X2 + 1 < n)
            mat[X2 + 1][0]--;
    }
 
    // Calculate the running sum
    int sum = 0;
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            sum += mat[i][j];
 
            // Print the updated element
            cout << sum << " ";
        }
 
        // Next line
        cout << endl;
    }
}
 
// Driver code
int main()
{
 
    // Size of the matrix
    int n = 5;
     
 
    // Queries
    int q[3][4] = {{ 0, 0, 1, 2 },
                   { 1, 2, 3, 4 },
                   { 1, 4, 3, 4 }};
 
    updateMatrix(n, q);
    return 0;
}
 
// This code is contributed by chandan_jnu

// Java implementation of the approach
public class GFG {
 
    // Function to update and print the matrix
    // after performing queries
    static void updateMatrix(int n, int q[][], int mat[][])
    {
        int i, j;
        for (i = 0; i < q.length; i++) {
            int X1 = q[i][0];
            int Y1 = q[i][1];
            int X2 = q[i][2];
            int Y2 = q[i][3];
 
            // Add 1 to the first element of the sub-matrix
            mat[X1][Y1]++;
 
            // If there is an element after the last element
            // of the sub-matrix then decrement it by 1
            if (Y2 + 1 < n)
                mat[X2][Y2 + 1]--;
            else if (X2 + 1 < n)
                mat[X2 + 1][0]--;
        }
 
        // Calculate the running sum
        int sum = 0;
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                sum += mat[i][j];
 
                // Print the updated element
                System.out.print(sum + " ");
            }
 
            // Next line
            System.out.println();
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
 
        // Size of the matrix
        int n = 5;
        int mat[][] = new int[n][n];
 
        // Queries
        int q[][] = { { 0, 0, 1, 2 },
                      { 1, 2, 3, 4 },
                      { 1, 4, 3, 4 } };
 
        updateMatrix(n, q, mat);
    }
}

# Python 3 implementation of the approach
 
# Function to update and print the matrix
# after performing queries
def updateMatrix(n, q, mat):
         
    for i in range(0, len(q)):
            X1 = q[i][0];
            Y1 = q[i][1];
            X2 = q[i][2];
            Y2 = q[i][3];
 
            # Add 1 to the first element of
            # the sub-matrix
            mat[X1][Y1] = mat[X1][Y1] + 1;
 
            # If there is an element after the
            # last element of the sub-matrix
            # then decrement it by 1
            if (Y2 + 1 < n):
                mat[X2][Y2 + 1] = mat[X2][Y2 + 1] - 1;
            elif (X2 + 1 < n):
                mat[X2 + 1][0] = mat[X2 + 1][0] - 1;
 
    # Calculate the running sum
    sum = 0;
    for i in range(0, n):
        for j in range(0, n):
            sum =sum + mat[i][j];
 
            # Print the updated element
            print(sum, end = ' ');
             
        # Next line
        print(" ");
         
# Driver code
 
# Size of the matrix
n = 5;
mat = [[0 for i in range(n)]
          for i in range(n)];
 
# Queries
q = [[ 0, 0, 1, 2 ],
     [ 1, 2, 3, 4 ],
     [ 1, 4, 3, 4 ]];
 
updateMatrix(n, q, mat);
     
# This code is contributed
# by Shivi_Aggarwal

// C# implementation of the above approach
 
using System;
 
public class GFG {
 
    // Function to update and print the matrix
    // after performing queries
    static void updateMatrix(int n, int [,]q, int [,]mat)
    {
        int i, j;
        for (i = 0; i < q.GetLength(0); i++) {
            int X1 = q[i,0];
            int Y1 = q[i,1];
            int X2 = q[i,2];
            int Y2 = q[i,3];
 
            // Add 1 to the first element of the sub-matrix
            mat[X1,Y1]++;
 
            // If there is an element after the last element
            // of the sub-matrix then decrement it by 1
            if (Y2 + 1 < n)
                mat[X2,Y2 + 1]--;
            else if (X2 + 1 < n)
                mat[X2 + 1,0]--;
        }
 
        // Calculate the running sum
        int sum = 0;
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                sum += mat[i,j];
 
                // Print the updated element
                Console.Write(sum + " ");
            }
 
            // Next line
            Console.WriteLine();
        }
    }
 
    // Driver code
    public static void Main()
    {
 
        // Size of the matrix
        int n = 5;
        int [,]mat = new int[n,n];
 
        // Queries
        int [,]q = { { 0, 0, 1, 2 },
                    { 1, 2, 3, 4 },
                    { 1, 4, 3, 4 } };
 
        updateMatrix(n, q, mat);
    }
    // This code is contributed by Ryuga
}

<?php
// PHP implementation of the approach
 
// Function to update and print the
// matrix after performing queries
function updateMatrix($n, $q, $mat)
{
    for ($i = 0; $i < sizeof($q); $i++)
    {
        $X1 = $q[$i][0];
        $Y1 = $q[$i][1];
        $X2 = $q[$i][2];
        $Y2 = $q[$i][3];
 
        // Add 1 to the first element of
        // the sub-matrix
        $mat[$X1][$Y1]++;
 
        // If there is an element after the last
        // element of the sub-matrix then decrement
        // it by 1
        if ($Y2 + 1 < $n)
            $mat[$X2][$Y2 + 1]--;
        else if ($X2 + 1 < $n)
            $mat[$X2 + 1][0]--;
    }
 
    // Calculate the running sum
    $sum = 0;
    for ($i = 0; $i < $n; $i++)
    {
        for ($j = 0; $j < $n; $j++)
        {
            $sum += $mat[$i][$j];
 
            // Print the updated element
            echo($sum . " ");
        }
 
        // Next line
        echo("\n");
    }
}
 
// Driver code
 
// Size of the matrix
$n = 5;
$mat = array_fill(0, $n,
       array_fill(0, $n, 0));
 
// Queries
$q = array(array( 0, 0, 1, 2 ),
           array( 1, 2, 3, 4 ),
           array( 1, 4, 3, 4 ));
 
updateMatrix($n, $q, $mat);
 
// This code is contributed by chandan_jnu
?>

<script>
    // Javascript implementation of the approach
     
    // Function to update and print the matrix
    // after performing queries
    function updateMatrix(n, q, mat)
    {
        let i, j;
        for (i = 0; i < q.length; i++) {
            let X1 = q[i][0];
            let Y1 = q[i][1];
            let X2 = q[i][2];
            let Y2 = q[i][3];
   
            // Add 1 to the first element of the sub-matrix
            mat[X1][Y1]++;
   
            // If there is an element after the last element
            // of the sub-matrix then decrement it by 1
            if (Y2 + 1 < n)
                mat[X2][Y2 + 1]--;
            else if (X2 + 1 < n)
                mat[X2 + 1][0]--;
        }
   
        // Calculate the running sum
        let sum = 0;
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                sum += mat[i][j];
   
                // Print the updated element
                document.write(sum + " ");
            }
   
            // Next line
            document.write("</br>");
        }
    }
     
    // Size of the matrix
    let n = 5;
    let mat = new Array(n);
    for(let i = 0; i < n; i++)
    {
        mat[i] = new Array(n);
        for(let j = 0; j < n; j++)
        {
            mat[i][j] = 0;
        }
    }
 
    // Queries
    let q = [ [ 0, 0, 1, 2 ],
              [ 1, 2, 3, 4 ],
              [ 1, 4, 3, 4 ] ];
 
    updateMatrix(n, q, mat);
     
    // This code is contributed by divyeshrabadiya07.
</script>

1 1 1 1 1 
1 1 2 1 2 
2 2 2 2 2 
2 2 2 2 2 
0 0 0 0 0

Complejidad temporal: O(n ² )

Espacio Auxiliar: O(n ² )