前缀和算法实战：连续数组与矩阵区域和

解法思路： 这是二维前缀和的典型应用。关键在于确定查询区域的左上角和右下角坐标，并处理好边界溢出情况。

对于点 (i, j)，其周围 k 范围内的区域边界需要限制在矩阵 [0, m-1] x [0, n-1] 内。

• 左上角坐标：x1 = max(0, i-k)，y1 = max(0, j-k)
• 右下角坐标：x2 = min(m-1, i+k)，y2 = min(n-1, j+k)

利用预处理好的二维前缀和数组 dp，可以在 O(1) 时间内计算任意矩形区域的和。注意下标映射关系，通常 dp 数组会比原矩阵多一行一列以简化边界判断。

C++ 代码实现：

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        vector<vector<int>> answer(m, vector<int>(n));
        
        // 构建二维前缀和
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + mat[i-1][j-1];
            }
        }
        
        // 计算结果
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                int x1 = max(0, i - k) + 1;
                int y1 = max(0, j - k) + 1;
                int x2 = min(m - 1, i + k) + 1;
                int y2 = min(n - 1, j + k) + 1;
                answer[i][j] = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1];
            }
        }
        return answer;
    }
};

这两道题虽然场景不同，但核心都是利用前缀和将重复计算转化为 O(1) 查询。实际写的时候容易忽略边界条件，尤其是二维前缀和下标的偏移量，建议画图辅助理解。