Given an n x n square matrix, find sums of all sub-squares of size k x k

Problem:
Given an n x n square matrix, find sums of all sub-squares of size k x k where k is smaller than or equal to n.
Examples:

Input:
n = 5, k = 3
arr[][] = { {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},
         };
Output:
       18  18  18
       27  27  27
       36  36  36


Input:
n = 3, k = 2
arr[][] = { {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9},
         };
Output:
       12  16
       24  28

Solution:
Pre-process the matrix by calculating sums of all vertical strips of size 1 x k. Note that you can use the "rolling window" approach to calculate subsequent sums in the same column in O(1) time.
Then use the calculated sums and, again, the rolling window approach to calculate the k x k squares' sums.


Complexity:

time - O(n^2)
space - O(n)

Links and credits:
http://www.geeksforgeeks.org/given-n-x-n-square-matrix-find-sum-sub-squares-size-k-x-k/