LeetCode 308 - Range Sum Query 2D - Mutable

作者 QIFAN 日期 2017-03-25
LeetCode 308 - Range Sum Query 2D - Mutable

原题链接:308. Range Sum Query 2D - Mutable


题干

给定一个 int 矩阵 matrix 。实现一个类 NumMatrix , API 如下:

public NumMatrix(int[][] matrix) \\ Constructor
public void update(int row, int col, int val) \\ 更新矩阵值
public int sumRegion(int row1, int col1, int row2, int col2) \\ 算出指定矩形范围的值的和

一个矩形由其左上角与右下角定义,比如下图红框矩形表示为 {(2,1), (4,3)} 。(2,1) 是左上角的坐标值,(4,3) 是右下角的坐标值。该矩形范围内的和 sum = 2 + 1 + 1 + 1 + 3 = 8 。
矩形示意

思路

构造器和更新很简单,算范围值用简单粗暴的加总也很容易,但是无疑是超时的,时间复杂度不行,如果 matrix 有 N 个格子,连续召唤 M 次 sumRegion ,最坏情况(每次都计算整个 matrix 的和)时间复杂度为 $O(M * N)$。我优化的想法是用一个缓存,但这样也挺复杂的,因为一个值的 update ,所有包含该点的矩阵值都要更新。看了 Tag 显示的是 Binary Index Tree ,从来没接触过这个结构,就直接看讨论学习了。

Binary Index Tree

油管上这个三哥哥讲的挺清楚的:



二维的 BIT 和一维的类似,设 BIT tree 的二维矩阵为 tree = new int[M][N]tree[i + 1][j + 1] 代表了 matrix 里以 (0,0) 为左上角,(i,j) 为右下角定义的矩形内所有值的和。

代码,reference:https://discuss.leetcode.com/topic/30343/java-2d-binary-indexed-tree-solution-clean-and-short-17ms

public class NumMatrix {
int[][] tree;
int[][] nums;
int m;
int n;
public NumMatrix(int[][] matrix) {
if (matrix.length == 0 || matrix[0].length == 0) return;
m = matrix.length;
n = matrix[0].length;
tree = new int[m+1][n+1];
nums = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
update(i, j, matrix[i][j]);
}
}
}
public void update(int row, int col, int val) {
if (m == 0 || n == 0) return;
int delta = val - nums[row][col];
nums[row][col] = val;
// i + i & (-i) 代表着包含这个点的下一个树
for (int i = row + 1; i <= m; i += i & (-i)) {
for (int j = col + 1; j <= n; j += j & (-j)) {
tree[i][j] += delta;
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
if (m == 0 || n == 0) return 0;
return sum(row2+1, col2+1) + sum(row1, col1) - sum(row1, col2+1) - sum(row2+1, col1);
}
public int sum(int row, int col) {
int sum = 0;
for (int i = row; i > 0; i -= i & (-i)) {
for (int j = col; j > 0; j -= j & (-j)) {
sum += tree[i][j];
}
}
return sum;
}
}
/**
* Your NumMatrix object will be instantiated and called as such:
* NumMatrix obj = new NumMatrix(matrix);
* obj.update(row,col,val);
* int param_2 = obj.sumRegion(row1,col1,row2,col2);
*/

设 matrix 里共有 N 个数,进行了 M 次 update 和 sumRegion 操作,时间复杂度为 $O(MlogN)$ 。