前缀和——矩阵区域和

一.题目描述

1314. 矩阵区域和 - 力扣（LeetCode）

二.题目解析

题目乍一看就是求个矩阵，仔细一看这矩阵砸球啊？题目叽里咕噜说什么呢？下面用图来展示一下，题目的要求：

 answer[i][j]位置的元素就是以mat对应位置为中心，然后k为半径的矩阵的和。

题目所求的矩阵， 本质就是需要求一段矩阵的和，所以快速求矩阵的和我们就可以使用二维前缀和来解决问题。

三.算法原理

二维前缀和

1.预处理二维前缀和数组

我们首先回顾一下二维前缀和数组每个位置表示的是什么：dp[i][j]表示的是原数组从(1,1)~(i,j)这个矩阵的和。

2.使用前缀和数组 

我们使用二维前缀和数组就可以求出原数组中某一段区间的和

接下里我们要将其融入到我们的answer中，answer求得也是一个区间的和，但是我们只知道中心下标，为了求这个区间的和，我们得知道这个区间的左上和右下的下标，依次来使用前缀和数组： 

但是需要注意的是，我们求这连个点的下标时，有可能会导致越界。就如示例一种answer的(0,0)位置的值，它的左上下标已经越界了，所以我们要对其进行处理。

如果左上的下标为负数了，其应该变为0；如果右下的下标大于n-1/m-1，就应该变为n-1/m-1。

这里有一个简单的方法来修正下标：

x1 = max(0,i-k),y1 = max(0,j-k)；x2 = min(n-1,i+k),y2 = min(m-1,j+k)

最后将该作坐标带入上面的公式即可。

3.细节处理

我们这里的mat数组是从0,0位置开始的。而我们在预处理dp数组时，为了避免边界情况(计算后的下标小于0)，下标是从1，1开始的。所以我们在预处理时加最后的d时，其实对应的是mat数组的mat[i-1][j-1]

还有就是使用dp数组时，answer返回数组的下标是从0,0开始的，而dp数组从1，1开始才是有效数据。我们计算下标是按照answer来计算的，而我们下标最后应用的数组却是dp数组。所以要给计算来的下标加上1.

x1 = max(0,i-k) + 1,y1 = max(0,j-k)+ 1；x2 = min(n-1,i+k)+ 1,y2 = min(m-1,j+k)+ 1.

时间复杂度：预处理二维数组时需要遍历一遍矩阵，后面使用二维数组都是常数级的时间复杂度，所以时间复杂度为O(MN)

空间复杂度：我们额外开了一个(m+1)*(n+1)大的空间来存储前缀和数组，所以空间复杂度为O(MN) 

四.代码实现

// C++

class Solution 
{
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) 
    {
        int m = mat.size();
        int n = mat[0].size();
        vector<vector<int>> answer(m,vector<int>(n));

        // 初始化dp数组
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        for(int i=1; i<m+1; ++i)
            for(int j=1; j<n+1; ++j)
                dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + mat[i-1][j-1];

        // 使用dp数组
        for(int i=0; i<m; ++i)
            for(int j=0; j<n; ++j)
            {
                int x1 = max(0,i-k) + 1, y1 = max(0,j-k) + 1;
                int x2 = min(m-1,i+k) + 1, y2 = min(n-1,j+k) + 1;

                answer[i][j] = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1];
            }
        return answer;
    }
};

# python

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

        # 预处理二维前缀和数组
        dp = [[0]*(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][j-1] + dp[i-1][j]+mat[i-1][j-1]-dp[i-1][j-1]
        
        # 使用前缀和数组
        for i in range(0,m):
            for j in range(0,n):
                x1,y1 = max(0,i-k) + 1,max(0,j-k) + 1
                x2,y2 = min(m-1,i+k) + 1,min(n-1,j+k) + 1
                answer[i][j] = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1]
        return answer