Final Matrix after incrementing submatrices by K in range given by Q queries | Javascript 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 ; Given Matrix ; Given Queries ; Function Call
let N = 3 ; let M = 4 ; class query { constructor ( x1 , x2 , y1 , y2 , k ) { this . x1 = x1 ; this . x2 = x2 ; this . y1 = y1 ; this . y2 = y2 ; this . K = k ; } } function updateQuery ( from_x , from_y , to_x , to_y , k , aux ) { 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 ; } function updateMatrix ( mat , aux ) { for ( let i = 0 ; i < N ; i ++ ) { for ( let j = 1 ; j < M ; j ++ ) { aux [ i ] [ j ] += aux [ i ] [ j - 1 ] ; } } for ( let i = 0 ; i < M ; i ++ ) { for ( let j = 1 ; j < N ; j ++ ) { aux [ j ] [ i ] += aux [ j - 1 ] [ i ] ; } } for ( let i = 0 ; i < N ; i ++ ) { for ( let j = 0 ; j < M ; j ++ ) { mat [ i ] [ j ] += aux [ i ] [ j ] ; } } } function printMatrix ( mat ) { for ( let i = 0 ; i < N ; i ++ ) { for ( let j = 0 ; j < M ; j ++ ) { document . write ( mat [ i ] [ j ] + " " ) ; } document . write ( " " ) ; } } function matrixQuery ( mat , Q , q ) { 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 ; } } for ( let 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 ) ; } let mat = [ [ 1 , 0 , 1 , 2 ] , [ 0 , 2 , 4 , 1 ] , [ 1 , 2 , 1 , 0 ] ] ; let Q = 1 ; let q = [ new query ( 0 , 0 , 1 , 1 , 2 ) ] ; matrixQuery ( mat , Q , q ) ;