Submatrix Sum Queries | Python 3 program to compute submatrix query sum in O ( 1 ) time ; Function to preprcess input mat [ M ] [ N ] . This function mainly fills aux [ M ] [ N ] such that aux [ i ] [ j ] stores sum of elements from ( 0 , 0 ) to ( i , j ) ; Copy first row of mat [ ] [ ] to aux [ ] [ ] ; Do column wise sum ; Do row wise sum ; A O ( 1 ) time function to compute sum of submatrix between ( tli , tlj ) and ( rbi , rbj ) using aux [ ] [ ] which is built by the preprocess function ; result is now sum of elements between ( 0 , 0 ) and ( rbi , rbj ) ; Remove elements between ( 0 , 0 ) and ( tli - 1 , rbj ) ; Remove elements between ( 0 , 0 ) and ( rbi , tlj - 1 ) ; Add aux [ tli - 1 ] [ tlj - 1 ] as elements between ( 0 , 0 ) and ( tli - 1 , tlj - 1 ) are subtracted twice ; Driver Code
M = 4 NEW_LINE N = 5 NEW_LINE def preProcess ( mat , aux ) : NEW_LINE INDENT for i in range ( 0 , N , 1 ) : NEW_LINE INDENT aux [ 0 ] [ i ] = mat [ 0 ] [ i ] NEW_LINE DEDENT for i in range ( 1 , M , 1 ) : NEW_LINE INDENT for j in range ( 0 , N , 1 ) : NEW_LINE INDENT aux [ i ] [ j ] = mat [ i ] [ j ] + aux [ i - 1 ] [ j ] NEW_LINE DEDENT DEDENT for i in range ( 0 , M , 1 ) : NEW_LINE INDENT for j in range ( 1 , N , 1 ) : NEW_LINE INDENT aux [ i ] [ j ] += aux [ i ] [ j - 1 ] NEW_LINE DEDENT DEDENT DEDENT def sumQuery ( aux , tli , tlj , rbi , rbj ) : NEW_LINE INDENT res = aux [ rbi ] [ rbj ] NEW_LINE if ( tli > 0 ) : NEW_LINE INDENT res = res - aux [ tli - 1 ] [ rbj ] NEW_LINE DEDENT if ( tlj > 0 ) : NEW_LINE INDENT res = res - aux [ rbi ] [ tlj - 1 ] NEW_LINE DEDENT if ( tli > 0 and tlj > 0 ) : NEW_LINE INDENT res = res + aux [ tli - 1 ] [ tlj - 1 ] NEW_LINE DEDENT return res NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT mat = [ [ 1 , 2 , 3 , 4 , 6 ] , [ 5 , 3 , 8 , 1 , 2 ] , [ 4 , 6 , 7 , 5 , 5 ] , [ 2 , 4 , 8 , 9 , 4 ] ] NEW_LINE DEDENT aux = [ [ 0 for i in range ( N ) ] for j in range ( M ) ] NEW_LINE preProcess ( mat , aux ) NEW_LINE tli = 2 NEW_LINE tlj = 2 NEW_LINE rbi = 3 NEW_LINE rbj = 4 NEW_LINE print ( " Query1 : " , sumQuery ( aux , tli , tlj , rbi , rbj ) ) NEW_LINE tli = 0 NEW_LINE tlj = 0 NEW_LINE rbi = 1 NEW_LINE rbj = 1 NEW_LINE print ( " Query2 : " , sumQuery ( aux , tli , tlj , rbi , rbj ) ) NEW_LINE tli = 1 NEW_LINE tlj = 2 NEW_LINE rbi = 3 NEW_LINE rbj = 3 NEW_LINE print ( " Query3 : " , sumQuery ( aux , tli , tlj , rbi , rbj ) ) NEW_LINE