1314

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        n = len(mat)
        m = len(mat[0])
        pref = [[0] * m for _ in range(n)]
        pref[0][0] = mat[0][0]

        for i in range(1, m):
            pref[0][i] = pref[0][i-1] + mat[0][i]

        for i in range(1, n):
            pref[i][0] = pref[i-1][0] + mat[i][0]

        for i in range(1, n):
            for j in range(1, m):
                pref[i][j] = pref[i][j-1] + pref[i-1][j] - pref[i-1][j-1] + mat[i][j]

        answer = [[0] * m for _ in range(n)]

        for i in range(n):
            for j in range(m):
                x1 = max(i-K, 0)
                x2 = min(i+K, n-1)
                y1 = max(j-K, 0)
                y2 = min(j+K, m-1)
                left = pref[x2][y1-1] if y1 > 0 else 0
                top = pref[x1-1][y2] if x1 > 0 else 0
                cross = pref[x1-1][y1-1] if x1 > 0 and y1 > 0 else 0
                answer[i][j] = pref[x2][y2] - left - top + cross

        return answer