LeetCode 304 Range Sum Query 2D - Immutable
概述
https://leetcode.com/problems/range-sum-query-2d-immutable/
暴力遍历法
不赘述，每次查询 O(n^2) 的时间复杂度，n 为区域长宽。
前缀和
与一维情况下一样的套路。
初始化 O(n^2)，每次查询 O(1)。
class NumMatrix {
public:
vector<vector<int>> sums;
NumMatrix(vector<vector<int>>& matrix) {
sums = matrix;
for (int i = 0; i < matrix.size(); i ++) {
for (int j = 0; j < matrix[0].size(); j ++) {
sums[i][j] = matrix[i][j];
if (i - 1 >= 0) sums[i][j] += sums[i-1][j];
if (j - 1 >= 0) sums[i][j] += sums[i][j-1];
if (i - 1 >= 0 && j - 1 >= 0) sums[i][j] -= sums[i-1][j-1];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
int ans = sums[row2][col2];
if (col1 - 1 >= 0) ans -= sums[row2][col1-1];
if (row1 - 1 >= 0) ans -= sums[row1-1][col2];
if (row1 - 1 >= 0 && col1 - 1 >= 0) ans += sums[row1-1][col1-1];
return ans;
}
};