Article / 文章
LeetCode 第308题：二维区域和检索-可变
给你一个二维矩阵 matrix ，你需要实现以下功能： 1. 更新某个单元格的值 2. 计算子矩阵元素的总和 实现 NumMatrix 类： - NumMatrix(int[][] matrix) 用整数矩阵 matrix 初始化对象 - void update(int row, int col, int val) 更新 matrix[row][col] 的
📖 文章摘要
本文详细解析LeetCode第308题“二维区域和检索-可变”，这是一道高级数据结构应用题。文章提供了基于二维树状数组（Binary Indexed Tree）的解决方案，包含C#、Python、C++三种语言实现，配有详细的原理分析和性能分析。适合对高级数据结构和动态查询优化感兴趣的读者。
核心知识点： 二维树状数组、区间查询、动态更新、前缀和
难度等级： 困难
推荐人群： 具有数据结构基础，想要提升高级数据结构应用能力的程序员
题目描述
给你一个二维矩阵 matrix ，你需要实现以下功能：
- 更新某个单元格的值
- 计算子矩阵元素的总和
实现 NumMatrix 类：
- NumMatrix(int[][] matrix) 用整数矩阵 matrix 初始化对象
- void update(int row, int col, int val) 更新 matrix[row][col] 的值到 val
- int sumRegion(int row1, int col1, int row2, int col2) 返回矩阵中(row1, col1)到(row2, col2)的子矩阵元素的和
示例
示例 1：
输入：
["NumMatrix", "sumRegion", "update", "sumRegion"]
[[[[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]], [2, 1, 4, 3], [3, 2, 2], [2, 1, 4, 3]]
输出：
[null, 8, null, 10]
解释：
NumMatrix numMatrix = new NumMatrix([[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]);
numMatrix.sumRegion(2, 1, 4, 3); // 返回 8
numMatrix.update(3, 2, 2); // matrix[3][2] 更新为 2
numMatrix.sumRegion(2, 1, 4, 3); // 返回 10提示
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 200
- -105 <= matrix[i][j] <= 105
- 0 <= row < m
- 0 <= col < n
- -105 <= val <= 105
- 0 <= row1 <= row2 < m
- 0 <= col1 <= col2 < n
- 最多调用 104 次 sumRegion 和 update 方法
解题思路
本题的核心是设计一个数据结构，能够同时支持单点更新和区域查询。二维树状数组（Binary Indexed Tree）是解决此类问题的最佳选择。
关键点：
- 使用二维树状数组维护矩阵前缀和
- 实现单点更新和区域查询操作
- 优化查询性能
具体步骤：
- 初始化二维树状数组
- 实现lowbit函数获取最低位1
- 实现update操作更新树状数组
- 实现query操作计算前缀和
- 通过前缀和差值计算区域和
图解思路
二维树状数组结构分析表
| 操作 | 数据结构 | 时间复杂度 | 说明 |
|---|---|---|---|
| 初始化 | 二维数组 | O(mn) | 构建树状数组 |
| 更新 | 树状数组 | O(logm * logn) | 更新单个元素 |
| 查询 | 树状数组 | O(logm * logn) | 计算区域和 |
操作流程分析表
| 步骤 | 操作 | 复杂度 | 说明 |
|---|---|---|---|
| 单点更新 | update | O(logm * logn) | 更新所有相关节点 |
| 前缀和查询 | query | O(logm * logn) | 计算(0,0)到(i,j)的和 |
| 区域和查询 | sumRegion | O(logm * logn) | 通过前缀和计算区域和 |
代码实现
C# 实现
public class NumMatrix {
private int[,] tree;
private int[,] matrix;
private int m, n;
public NumMatrix(int[][] matrix) {
if (matrix.Length == 0 || matrix[0].Length == 0) return;
m = matrix.Length;
n = matrix[0].Length;
this.matrix = new int[m,n];
tree = new int[m+1,n+1];
// 初始化树状数组
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
Update(i, j, matrix[i][j]);
}
}
}
private int LowBit(int x) {
return x & (-x);
}
public void Update(int row, int col, int val) {
int diff = val - matrix[row,col];
matrix[row,col] = val;
for (int i = row + 1; i <= m; i += LowBit(i)) {
for (int j = col + 1; j <= n; j += LowBit(j)) {
tree[i,j] += diff;
}
}
}
private int Query(int row, int col) {
int sum = 0;
for (int i = row; i > 0; i -= LowBit(i)) {
for (int j = col; j > 0; j -= LowBit(j)) {
sum += tree[i,j];
}
}
return sum;
}
public int SumRegion(int row1, int col1, int row2, int col2) {
return Query(row2 + 1, col2 + 1)
- Query(row2 + 1, col1)
- Query(row1, col2 + 1)
+ Query(row1, col1);
}
}Python 实现
class NumMatrix:
def __init__(self, matrix: List[List[int]]):
if not matrix or not matrix[0]:
return
self.matrix = [[0] * len(matrix[0]) for _ in range(len(matrix))]
self.m, self.n = len(matrix), len(matrix[0])
self.tree = [[0] * (self.n + 1) for _ in range(self.m + 1)]
for i in range(self.m):
for j in range(self.n):
self.update(i, j, matrix[i][j])
def lowbit(self, x: int) -> int:
return x & (-x)
def update(self, row: int, col: int, val: int) -> None:
diff = val - self.matrix[row][col]
self.matrix[row][col] = val
i = row + 1
while i <= self.m:
j = col + 1
while j <= self.n:
self.tree[i][j] += diff
j += self.lowbit(j)
i += self.lowbit(i)
def query(self, row: int, col: int) -> int:
total = 0
i = row
while i > 0:
j = col
while j > 0:
total += self.tree[i][j]
j -= self.lowbit(j)
i -= self.lowbit(i)
return total
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
return (self.query(row2 + 1, col2 + 1)
- self.query(row2 + 1, col1)
- self.query(row1, col2 + 1)
+ self.query(row1, col1))C++ 实现
class NumMatrix {
private:
vector<vector<int>> tree;
vector<vector<int>> matrix;
int m, n;
int lowbit(int x) {
return x & (-x);
}
int query(int row, int col) {
int sum = 0;
for (int i = row; i > 0; i -= lowbit(i)) {
for (int j = col; j > 0; j -= lowbit(j)) {
sum += tree[i][j];
}
}
return sum;
}
public:
NumMatrix(vector<vector<int>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return;
m = matrix.size();
n = matrix[0].size();
this->matrix = vector<vector<int>>(m, vector<int>(n, 0));
tree = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
update(i, j, matrix[i][j]);
}
}
}
void update(int row, int col, int val) {
int diff = val - matrix[row][col];
matrix[row][col] = val;
for (int i = row + 1; i <= m; i += lowbit(i)) {
for (int j = col + 1; j <= n; j += lowbit(j)) {
tree[i][j] += diff;
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
return query(row2 + 1, col2 + 1)
- query(row2 + 1, col1)
- query(row1, col2 + 1)
+ query(row1, col1);
}
};执行结果
C# 实现
- 执行用时：232 ms
- 内存消耗：58.2 MB
Python 实现
- 执行用时：296 ms
- 内存消耗：25.8 MB
C++ 实现
- 执行用时：184 ms
- 内存消耗：42.6 MB
性能对比
| 语言 | 执行用时 | 内存消耗 | 特点 |
|---|---|---|---|
| C# | 232 ms | 58.2 MB | 性能适中，内存占用较大 |
| Python | 296 ms | 25.8 MB | 执行较慢，内存占用最小 |
| C++ | 184 ms | 42.6 MB | 执行最快，内存占用适中 |
代码亮点
- 🎯 使用二维树状数组实现高效的区域和查询
- 💡 通过lowbit优化树状数组的更新和查询操作
- 🔍 利用前缀和差值计算任意矩形区域的和
- 🎨 代码结构清晰，各个功能模块分离
常见错误分析
- 🚫 忽略矩阵为空的边界情况
- 🚫 树状数组索引计算错误
- 🚫 更新操作未考虑差值
- 🚫 区域和计算时前缀和相减顺序错误
解法对比
| 解法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 二维前缀和 | O(mn) 初始化, O(1) 查询, O(mn) 更新 | O(mn) | 查询快速 | 更新慢 |
| 二维树状数组 | O(mn) 初始化, O(logm*logn) 查询和更新 | O(mn) | 更新和查询都较快 | 实现复杂 |
| 线段树 | O(mn) 初始化, O(logm*logn) 查询和更新 | O(mn) | 功能强大 | 代码复杂度高 |
相关题目
- LeetCode 304. 二维区域和检索 - 矩阵不可变 - 中等
- LeetCode 307. 区域和检索 - 数组可修改 - 中等
- LeetCode 315. 计算右侧小于当前元素的个数 - 困难
📖 系列导航
🔥 算法专题合集 - 查看完整合集
📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第308题。
💬 互动交流
感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。
如果这篇文章对你有帮助，请：
- 👍 点个赞，让更多人看到这篇文章
- 📁 收藏文章，方便后续查阅复习
- 🔔 关注作者，获取更多高质量算法题解
- 💭 评论区留言，分享你的解题思路或提出疑问
你的支持是我持续分享的动力！
💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！