C++ compact prefix sum explained 65% Speed, 100% Memory
For all possible row ranges, calculate cumulative matrix sums column by column identifying when sum equals target or when sum equals a previous sum (in the same
For all possible row ranges, calculate cumulative matrix sums column by column identifying when sum equals target or when sum equals a previous sum (in the same row range) minus the target. In the y direction, the cumulative sum is added to each column incrementally using a vector representing the column sum of interest in the row.\n\n```\nclass Solution {\npublic:\n    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {\n        int m = matrix.size();\n        int n = matrix[0].size();\n        int count = 0;\n        \n        for (int i = 0; i < m; i++){                      //Iterating over all possible row ranges between row i and row j\n            vector<int> CumulativeColumns = matrix[i];    //Instead of setting up a prefix sum matrix, add to columns as we go row by row\n            \n            for (int j = i; j < m; j++){\n                unordered_map<int,int> sumCount;          //track occurrences of corner matrix sums for the current row range\n                int totalSum = 0;\n                \n                for (int k = 0; k < n; k++){\n                    totalSum += CumulativeColumns[k];        //within the current row range, at every row cumulatively build matrix sums using cumulative column sums column by column\n                    if (totalSum == target) count++;         //if the target is found or if a sum is found that has a difference with a previous sum in the same top/bottom bounds exactly equal to target, add submatrices found\n                    if (sumCount.count(totalSum-target)) count += sumCount[totalSum-target];\n                    sumCount[totalSum]++;                    //Store the current cumulative sum to be used later in the row to calculate target matrix counts        \n                    if (j < m - 1) CumulativeColumns[k] += matrix[j+1][k];   //Increment the cumulative column sum for the next row iteration in the current row range if necessary\n                }\n            }\n        }\n        return count;\n    }\n};\n```
[]