Two Dimensional Difference Array | Python3 Program to implement the above approach ; Function to initialize the difference array ; Function to add k to the specified submatrix ( r1 , c1 ) to ( r2 , c2 ) ; Function to print the modified array ; Function to perform the given queries ; Difference array ; Function to initialize the difference array ; Count of queries ; Perform Queries ; Driver Code ; Given Matrix ; Given Queries
N = 3 NEW_LINE M = 3 NEW_LINE def intializeDiff ( D , A ) : NEW_LINE INDENT for i in range ( N ) : NEW_LINE INDENT D [ i ] [ 0 ] = A [ i ] [ 0 ] ; NEW_LINE D [ i ] [ M ] = 0 ; NEW_LINE DEDENT for i in range ( N ) : NEW_LINE INDENT for j in range ( 1 , M ) : NEW_LINE INDENT D [ i ] [ j ] = A [ i ] [ j ] - A [ i ] [ j - 1 ] ; NEW_LINE DEDENT DEDENT DEDENT def update ( D , k , r1 , c1 , r2 , c2 ) : NEW_LINE INDENT for i in range ( r1 , r2 + 1 ) : NEW_LINE INDENT D [ i ] [ c1 ] += k ; NEW_LINE D [ i ] [ c2 + 1 ] -= k ; NEW_LINE DEDENT DEDENT def printArray ( A , D ) : NEW_LINE INDENT for i in range ( N ) : NEW_LINE INDENT for j in range ( M ) : NEW_LINE INDENT if ( j == 0 ) : NEW_LINE INDENT A [ i ] [ j ] = D [ i ] [ j ] ; NEW_LINE DEDENT else : NEW_LINE INDENT A [ i ] [ j ] = D [ i ] [ j ] + A [ i ] [ j - 1 ] ; NEW_LINE DEDENT print ( A [ i ] [ j ] , end = ' ▁ ' ) NEW_LINE DEDENT print ( ) NEW_LINE DEDENT DEDENT def performQueries ( A , Queries ) : NEW_LINE INDENT D = [ [ 0 for j in range ( M + 1 ) ] for i in range ( N ) ] NEW_LINE intializeDiff ( D , A ) ; NEW_LINE Q = len ( Queries ) NEW_LINE for i in range ( Q ) : NEW_LINE INDENT update ( D , Queries [ i ] [ 0 ] , Queries [ i ] [ 1 ] , Queries [ i ] [ 2 ] , Queries [ i ] [ 3 ] , Queries [ i ] [ 4 ] ) ; NEW_LINE DEDENT printArray ( A , D ) ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT A = [ [ 1 , 2 , 3 ] , [ 1 , 1 , 0 ] , [ 4 , - 2 , 2 ] ] ; NEW_LINE Queries = [ [ 2 , 0 , 0 , 1 , 1 ] , [ - 1 , 1 , 0 , 2 , 2 ] ] ; NEW_LINE performQueries ( A , Queries ) ; NEW_LINE DEDENT