1314. Matrix Block Sum - cocoder39/coco39_LC GitHub Wiki
+-----+-+-------+ +--------+-----+ +-----+---------+ +-----+--------+
| | | | | | | | | | | | |
| | | | | | | | | | | | |
+-----+-+ | +--------+ | | | | +-----+ |
| | | | = | | + | | | - | | + mat[i][j]
+-----+-+ | | | +-----+ | | |
| | | | | | | |
| | | | | | | |
+---------------+ +--------------+ +---------------+ +--------------+
rangeSum[i+1][j+1] = rangeSum[i][j+1] + rangeSum[i+1][j] - rangeSum[i][j] + mat[i][j]
+---------------+ +--------------+ +---------------+ +--------------+ +--------------+
| | | | | | | | | | | | | |
| (r1,c1) | | | | | | | | | | | | |
| +------+ | | | | | | | +---------+ | +---+ |
| | | | = | | | - | | | - | (r1,c2) | + | (r1,c1) |
| | | | | | | | | | | | | |
| +------+ | +---------+ | +---+ | | | | |
| (r2,c2)| | (r2,c2)| | (r2,c1) | | | | |
+---------------+ +--------------+ +---------------+ +--------------+ +--------------+
to get answer[i][j], we need
- range sum that could cover mat[i+k][j+k], which is dp[i+k+1][j+k+1]
- range sum that could cover mat[i-k-1][j-k-1], which is dp[i-k][j-k]
def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
m, n = len(mat), len(mat[0])
dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + mat[i-1][j-1]
answer = [[0 for _ in range(n)] for _ in range(m)]
for i in range(m):
for j in range(n):
r1, c1 = max(0, i - k), max(0, j-k)
r2, c2 = min(m, i+k+1), min(n, j+k+1)
answer[i][j] = dp[r2][c2] + dp[r1][c1] - dp[r1][c2] - dp[r2][c1]
return answer