2D prefix sum
Given a large 2D array of numbers with
r rows and c columns, you are asked to calculate the 2D prefix sum of that matrix. 2D prefix sum at a location (r, c) is the sum of all the elements between the corner (0, 0) and the element (r, c). In other words, it’s the sum of elements of the submatrix with corners (0, 0), (r, 0), (r, c), and (0, c).Can you calculate the 2D prefix sum for all the locations in the matrix efficiently?
+ | + | + | + | ㅤ | ㅤ | ㅤ |
+ | + | + | + | ㅤ | ㅤ | ㅤ |
+ | + | + | + | ㅤ | ㅤ | ㅤ |
+ | + | + | + | ㅤ | ㅤ | ㅤ |
ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ |
ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ |
Input
The first line of the input contains two integers - the number of rows in the matrix
r and the number of columns c (1 ≤ r, c ≤ 1000).The next
r lines contain c integers separated by a space, that represent the elements in the matrix .Output
The program should print
r lines containing c numbers representing the 2D prefix sum matrix.Examples
Input | Output |
3 5
1 2 -3 4 6
-1 3 8 4 0
0 1 -2 0 5 | 1 3 0 4 10
0 5 10 18 24
0 6 9 17 28 |
Constraints
Time limit: 6 seconds
Memory limit: 512 MB
Output limit: 15 MB