Final Matrix after incrementing submatrices by K in range given by Q queries | C ++ program for the above approach ; Query data type ; Function to update the given query ; Update top cell ; Update bottom left cell ; Update bottom right cell ; Update top right cell ; Function that updates the matrix mat [ ] [ ] by adding elements of aux [ ] [ ] ; Compute the prefix sum of all columns ; Compute the prefix sum of all rows ; Get the final matrix by adding mat and aux matrix at each cell ; Function that prints matrix mat [ ] ; Traverse each row ; Traverse each columns ; Function that performs each query in the given matrix and print the updated matrix after each operation performed ; Initialize all elements to 0 ; Update auxiliary matrix by traversing each query ; Update Query ; Compute the final answer ; Print the updated matrix ; Driver Code ; Given Matrix ; Given Queries ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  3 NEW_LINE #define M  4 NEW_LINE struct query { int x1 , x2 , y1 , y2 , K ; } ; void updateQuery ( int from_x , int from_y , int to_x , int to_y , int k , int aux [ ] [ M ] ) { aux [ from_x ] [ from_y ] += k ; if ( to_x + 1 < N ) aux [ to_x + 1 ] [ from_y ] -= k ; if ( to_x + 1 < N && to_y + 1 < M ) aux [ to_x + 1 ] [ to_y + 1 ] += k ; if ( to_y + 1 < M ) aux [ from_x ] [ to_y + 1 ] -= k ; } void updateMatrix ( int mat [ ] [ M ] , int aux [ ] [ M ] ) { for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 1 ; j < M ; j ++ ) { aux [ i ] [ j ] += aux [ i ] [ j - 1 ] ; } } for ( int i = 0 ; i < M ; i ++ ) { for ( int j = 1 ; j < N ; j ++ ) { aux [ j ] [ i ] += aux [ j - 1 ] [ i ] ; } } for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < M ; j ++ ) { mat [ i ] [ j ] += aux [ i ] [ j ] ; } } } void printMatrix ( int mat [ ] [ M ] ) { for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < M ; j ++ ) { cout << mat [ i ] [ j ] << " ▁ " ; } cout << " STRNEWLINE " ; } } void matrixQuery ( int mat [ ] [ M ] , int Q , query q [ ] ) { int aux [ N ] [ M ] = { } ; for ( int i = 0 ; i < Q ; i ++ ) { updateQuery ( q [ i ] . x1 , q [ i ] . x2 , q [ i ] . y1 , q [ i ] . y2 , q [ i ] . K , aux ) ; } updateMatrix ( mat , aux ) ; printMatrix ( mat ) ; } int main ( ) { int mat [ N ] [ M ] = { { 1 , 0 , 1 , 2 } , { 0 , 2 , 4 , 1 } , { 1 , 2 , 1 , 0 } } ; int Q = 1 ; query q [ ] = { { 0 , 0 , 1 , 1 , 2 } } ; matrixQuery ( mat , Q , q ) ; return 0 ; }