# C++ with helper

• 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

``````                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.

• 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!

• `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 :-)

• 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!

• you are super genius !!! thank you .

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