aboutsummaryrefslogtreecommitdiff
path: root/range_sum_query_2d.cpp
blob: d50ea14f6cd35f52e23c3bb2452220e96f652164 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include "leetcode.h"

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

int main() {}