C++ with helper


  • 12

    My accu[i][j] is the sum of matrix[0..i][0..j], and a(i, j) helps with edge cases.

    class NumMatrix {
    public:
        NumMatrix(vector<vector<int>> &matrix) {
            accu = matrix;
            for (int i=0; i<matrix.size(); ++i)
                for (int j=0; j<matrix[0].size(); ++j)
                    accu[i][j] += a(i-1, j) + a(i, j-1) - a(i-1, j-1);
        }
    
        int sumRegion(int row1, int col1, int row2, int col2) {
            return a(row2, col2) - a(row1-1, col2) - a(row2, col1-1) + a(row1-1, col1-1);
        }
    
    private:
        vector<vector<int>> accu;
        int a(int i, int j) {
            return i >= 0 && j >= 0 ? accu[i][j] : 0;
        }
    };
    

    Afterthought

    Instead of

                    accu[i][j] += a(i-1, j) + a(i, j-1) - a(i-1, j-1);
    

    I could use

                    accu[i][j] += a(i, j) - sumRegion(i, j, i, j);
    

    which is shorter but I think less clear. I do like already using sumRegion in the precomputation, though.


  • 0

    Hi, Stefan. The helper a is really elegant :-)

    Well, I really cannot understand accu[i][j] += a(i, j) - sumRegion(i, j, i, j);: sumRegion(i, j, i, j) is just matrix[i][j] and thus also equal to accu[i][j] and a(i, j) before its update? If so, the rhs will become 0? There must be something wrong with my understanding. Could you give me some explanations? Thanks!


  • 0

    sumRegion(i, j, i, j) is just matrix[i][j]

    That's what it's supposed to be, but that's not how it's computed. Its actual computation involves accu[i][j], which isn't ready yet - it should be sum(matrix[0..i][0..j]) but it's only matrix[i][j] at that point. So accu[i][j] is missing the whole top/left part. Since sumRegion(i, j, i, j) uses it, it's also missing the whole top/left part and is thus matrix[i][j] minus the whole top/left part. If I negate it, it's the whole top/left part minus matrix[i][j]. By adding 2*matrix[i][j] (which is what my code line does), I get sum(matrix[0..i][0..j]).

    But in reality that's not what I thought. I just saw that the precomputation line and the query line were similar, and found out how to call sumRegion in order to make it work. I found the above explanation only now :-)


  • 0

    Oh, cool! I got it now. The sumRegion also uses accu[i][j] and thus at that point sumRegion(i, j, i, j) is not really matrix[i][j], but with the top/left part subtracted. Cool!


  • 0
    R

    you are super genius !!! thank you .


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.