传送门
二维前缀和，定义f[i][j]为从矩阵左上角(0,0)到当前位置(i-1,j-1)的元素之和，那么任意一个3×3小矩阵内的9个元素之和就是tot=f[i+2][j+2] – f[i+2][j-1] – f[i-1][j+2] + f[i-1][j-1]
提一下这个状态转移方程需要注意的几个点：因为多减了一次f[i-1][j-1]，所以要加回来；f[i][j]做了下标偏移是因为需要用到f[i+2][j-1]和f[i-1][j+2]来计算区域和。

class Solution {
public:
    vector<vector<int>> imageSmoother(vector<vector<int>>& img) {
        int m = img.size();
        int n = img[0].size();
        vector<vector<int>> f(m+1, vector<int>(n+1));
        vector<vector<int>> ans(m, vector<int>(n));

        // 二维前缀和
        // f[i][j]表示从(0,0)到(i-1,j-1)的区域内元素之和
        // 比起传统的二维前缀和，做了下标偏移
        // 因为后面计算时需要用到f[lx][ry+1]和f[rx+1][ly]计算区域和
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                f[i][j] = f[i-1][j] + f[i][j-1] - f[i-1][j-1] + img[i-1][j-1];
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int rx = min(m-1, i+1); // 右下角x
                int ry = min(n-1, j+1); // 右下角y
                int lx = max(0, i-1); // 左上角x
                int ly = max(0, j-1); // 左上角y
                // (0,0)到(i,j)的区域和减去(0,0)到(i-2,j)的区域和再减去(0,0)到(i,j-2)的和，
                // 最后再加上多减了的(0,0)到(i-2,j-2)的和
                int tot = f[rx+1][ry+1] - f[lx][ry+1] - f[rx+1][ly] + f[lx][ly];

                ans[i][j] = (int)(tot / ((rx - lx + 1) * (ry - ly + 1))); 
            }
        }

        return ans;
    }
};