0304. Range Sum Query 2D - Immutable
====================================
题目信息
--------
:题号: 0304
:难度: Medium
:主题: 矩阵、矩形区域和、只读对象、多次查询
:原题: `LeetCode 0304 `_
:重点: 矩形包含四条边界、坐标从零开始、构造后矩阵不更新、每次查询要求常数时间
题目重述
--------
实现 ``NumMatrix`` 类。构造函数接收整数矩阵 ``matrix``;之后可以多次调用 ``sumRegion(row1, col1, row2, col2)``,返回左上角 ``(row1, col1)`` 到右下角 ``(row2, col2)`` 所围闭合矩形中的元素总和,边界上的格子也必须计入。
矩阵行数和列数均位于 ``[1, 200]``,元素位于 ``[-10^5, 10^5]``。查询坐标满足 ``0 <= row1 <= row2 < rows`` 和 ``0 <= col1 <= col2 < columns``,调用次数不超过 ``10^4``。矩阵在构造后不会更新,并要求每次 ``sumRegion`` 查询在 ``O(1)`` 时间内完成。
自建示例
--------
查询跨越多行多列的矩形:
.. code-block:: text
输入:NumMatrix([
[2, -1, 4],
[0, 3, 5],
[7, 1, -2]
])
sumRegion(0, 1, 2, 2)
输出:10
解释:所选区域包含 -1、4、3、5、1、-2,总和为 10。
查询单个格子:
.. code-block:: text
输入:在上述对象上调用 sumRegion(2, 0, 2, 0)
输出:7
解释:两个角坐标相同,矩形只包含第 2 行第 0 列的元素 7。
二维前缀和与容斥
----------------
定义 ``prefix[r][c]`` 为左上角 ``(0, 0)`` 到 ``(r-1, c-1)`` 的矩形和,多出的第 0 行和第 0 列全部设为零。构造时使用二维前缀公式:当前矩形包含上方和左方区域,但左上角区域被重复计算,因此要减去一次,再加回当前格子。
查询闭矩形 ``[row1, row2] × [col1, col2]`` 时,先取 ``(0, 0)`` 到右下角的大矩形,减去上方和左方两个越界区域,再把左上角被减掉两次的区域加回来。前缀表多一行一列后,边界对应的下标都能直接写成 ``row + 1``、``col + 1``,无需为第一行或第一列写特殊分支。
C++ 实现
--------
.. code-block:: cpp
class NumMatrix {
std::vector> prefix;
public:
NumMatrix(std::vector>& matrix) {
int rows = static_cast(matrix.size());
int cols = static_cast(matrix[0].size());
prefix.assign(rows + 1, std::vector(cols + 1, 0));
for (int r = 1; r <= rows; ++r) {
for (int c = 1; c <= cols; ++c) {
prefix[r][c] = matrix[r - 1][c - 1]
+ prefix[r - 1][c]
+ prefix[r][c - 1]
- prefix[r - 1][c - 1];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
long long total = prefix[row2 + 1][col2 + 1]
- prefix[row1][col2 + 1]
- prefix[row2 + 1][col1]
+ prefix[row1][col1];
return static_cast(total);
}
};
代码分析
--------
``prefix`` 的每一个单元都代表固定的左上角区域,因此查询只需四次取值和三次加减,边界格子也不会漏算或重复计算。矩阵只读时,预处理的 ``O(rows * cols)`` 成本可以由多次查询共同承担;每次查询为 ``O(1)``,额外空间为 ``O(rows * cols)``。