C++ prefix sum, explanation with pictures (424ms / 9Mb)
The problem is split in two parts. \nFirst, compute 2D prefix sum matrix ps, so that element p[i][j] is equal to the sum of elements in submatrix matrix[x][y] w
The problem is split in two parts. \nFirst, compute 2D prefix sum matrix ```ps```, so that element ```p[i][j]``` is equal to the sum of elements in submatrix ```matrix[x][y]``` with ```0 <= x <= i, 0 <= y <= j```. For this purpose we compute 1D prefix sums for the first row and first column and then use the formula:\n```ps[i][j] = matrix[i][j] + ps[i-1][j] + ps[i][j-1] - ps[i-1][j-1]```\n\n\nHere is illustration:\n<img src="https://assets.leetcode.com/users/images/fad46894-4b59-48a9-a0f8-a6e969cc7b29_1618664366.132954.png" alt="drawing" height="200"/>\n\nThe sum of elements from ```(0,0)``` to ```(i,j)``` consists of element ```matrix[i][j]``` and sums of elemnts in submatrices ```A,B,C```. \n\nSum of elements in ```A``` is simply ```ps[i-1][j-1]```.\nElements in ```B```: ```ps[i][j-1] - ps[i-1][j-1]```.\nElements in ```C```: ```ps[i-1][j] - ps[i-1][j-1]```.\nSumming of all this \n\nSecond part of the solution: use the prefix sum matrix to quickly compute sums of all the possible submatrices:\n<img src="https://assets.leetcode.com/users/images/1d8e4609-5d06-4ad8-b97e-9f4af78e9906_1618665165.0758274.png" alt="drawing" height="250"/>\nSum of elements in submatrix ```matrix[x][y]``` with ```i0 <= x <= i1, j0 <= y <= j1``` is a difference between elements in ```D``` and elements in ```A```,```B``` and ```C```.  \n\nSum in ```D``` and ```A``` are prefix sums ```ps[i1][j1]``` and ```ps[i0-1][j0-1]```. For the remaining two submatrices we get:\n```B=ps[i1][j0-1] - ps[i0-1][j0-1]```\n```C=ps[i0-1][j1] - ps[i0-1][j0-1]```\n\nHence, the final formula is:\n```sum = ps[i1][j1]-ps[i1][j0-1]-ps[i0-1][j1]+ps[i0-1][j0-1]```\n\nThe corner cases are when ```j0=0``` or ```i0=0```.\n\n```\nclass Solution {\n    int ps[101][101];\npublic:\n    int numSubmatrixSumTarget(vector<vector<int>>& M, int target) {\n        ios_base::sync_with_stdio(false);\n        size_t n{ M.size() }, m{ M[0].size() };\n        \n\t\t// compute prefix sum\n        ps[0][0] = M[0][0];\n        for (int i = 1; i < n; i++) ps[i][0] = M[i][0] + ps[i-1][0];\n        for (int j = 1; j < m; j++) ps[0][j] = M[0][j] + ps[0][j-1];\n        \n        for (int i = 1; i < n; i++)\n            for (int j = 1; j < m; j++)\n                ps[i][j] = M[i][j] + ps[i-1][j] + ps[i][j-1] - ps[i-1][j-1];\n\n        \n        int count{};\n        // test all submatrices\n        for (int i0 = 0; i0 < n; i0++)\n            for (int j0 = 0; j0 < m; j0++)\n                for (int i1 = i0; i1 < n; i1++)\n                    for (int j1 = j0; j1 < m; j1++) {\n                        int sum{ ps[i1][j1] };\n\n                        if (i0 > 0) sum -= ps[i0 - 1][j1];\n                        if (j0 > 0) sum -= ps[i1][j0-1];\n                        if (i0 > 0 && j0 > 0) sum += ps[i0 - 1][j0 - 1];\n\n                        if (sum == target) count++;\n                    }\n\n        return count;\n    }\n};\n```
[]