Given an n x n square matrix , find sum of all sub | Size of given matrix ; A O ( n ^ 2 ) function to find sum of all sub - squares of size k x k in a given square matrix of size n x n ; k must be smaller than or equal to n ; 1 : PREPROCESSING To store sums of all strips of size k x 1 ; Go column by column ; Calculate sum of first k x 1 rectangle in this column ; Calculate sum of remaining rectangles ; 2 : CALCULATE SUM of Sub - Squares using stripSum [ ] [ ] ; Calculate and prsum of first subsquare in this row ; Calculate sum of remaining squares in current row by removing the leftmost strip of previous sub - square and adding a new strip ; Driver Code
n = 5 NEW_LINE def printSumTricky ( mat , k ) : NEW_LINE INDENT global n NEW_LINE if k > n : NEW_LINE INDENT return NEW_LINE DEDENT stripSum = [ [ None ] * n for i in range ( n ) ] NEW_LINE for j in range ( n ) : NEW_LINE INDENT Sum = 0 NEW_LINE for i in range ( k ) : NEW_LINE INDENT Sum += mat [ i ] [ j ] NEW_LINE DEDENT stripSum [ 0 ] [ j ] = Sum NEW_LINE for i in range ( 1 , n - k + 1 ) : NEW_LINE INDENT Sum += ( mat [ i + k - 1 ] [ j ] - mat [ i - 1 ] [ j ] ) NEW_LINE stripSum [ i ] [ j ] = Sum NEW_LINE DEDENT DEDENT for i in range ( n - k + 1 ) : NEW_LINE INDENT Sum = 0 NEW_LINE for j in range ( k ) : NEW_LINE INDENT Sum += stripSum [ i ] [ j ] NEW_LINE DEDENT print ( Sum , end = " ▁ " ) NEW_LINE for j in range ( 1 , n - k + 1 ) : NEW_LINE INDENT Sum += ( stripSum [ i ] [ j + k - 1 ] - stripSum [ i ] [ j - 1 ] ) NEW_LINE print ( Sum , end = " ▁ " ) NEW_LINE DEDENT print ( ) NEW_LINE DEDENT DEDENT mat = [ [ 1 , 1 , 1 , 1 , 1 ] , [ 2 , 2 , 2 , 2 , 2 ] , [ 3 , 3 , 3 , 3 , 3 ] , [ 4 , 4 , 4 , 4 , 4 ] , [ 5 , 5 , 5 , 5 , 5 ] ] NEW_LINE k = 3 NEW_LINE printSumTricky ( mat , k ) NEW_LINE