一、题目

1、题目描述

给你一个 2D 矩阵 matrix，请计算出从左上角 (row1, col1) 到右下角 (row2, col2) 组成的矩形中所有元素的和。

实现 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) 返回矩阵 matrix 中指定矩形区域元素的 和 ，该区域由 左上角 (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); // 矩阵从左图变为右图
numMatrix.sumRegion(2, 1, 4, 3); // 返回 10 (即，右侧红色矩形的和)注意:
矩阵 matrix 的值只能通过 update 函数来进行修改
你可以默认 update 函数和 sumRegion 函数的调用次数是均匀分布的
你可以默认 row1 ≤ row2，col1 ≤ col2

2、基础框架

3、原题链接

308. 二维区域和检索 - 可变

二、解题报告

1、思路分析

所谓的Index Tree的二维结构，单点更新指的是在二维数组中修改某个位置的值；而区间和查询指的是以二维数组的 (1,1) 位置((0,0) 位置弃用）为左上角，(i,j) 位置为右下角围成的矩形中的数据和。

同理，当二维数组中的某个位置值发生改变时，影响到的数据相应可能更多。

假设二维数组中的 (i,j) 位置的值发生改变，
而行 i 对应的二进制形式为 0110100，则受影响的范围是行的【0110001 ~ 0110100】
而列 j 对应的二进制形式为 0111000，则受影响的范围是列的【0110001 ~ 0111000】
该行列范围内的所有组合都受影响，即 0110001 行的 【0110001 ~ 01111000】列受影响，0110010 行的 0110001 ~ 01111000 列受影响，以此类推。
即受到影响的范围是 【行的二进制形式最后一个1去掉然后加1 ~ 行的二进制】 和 【列的二进制形式最后一个1去掉然后加1 ~ 列的二进制】

三维的也是同理。

2、时间复杂度

O(log行∗log列）O(log行 * log列）O(log行∗log列）

3、代码详解

// 测试链接：https://leetcode.com/problems/range-sum-query-2d-mutable
// 但这个题是付费题目
public class NumMatrix {private int[][] tree;private int[][] nums;private int N;private int M;public NumMatrix(int[][] matrix) {if (matrix.length == 0 || matrix[0].length == 0) {return;}N = matrix.length;M = matrix[0].length;tree = new int[N + 1][M + 1];nums = new int[N][M];for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {update(i, j, matrix[i][j]);}}}//累加和//计算左上角为(1,1)，右下角为(i,j)围成区域的累加和private int sum(int row, int col) {int sum = 0;for (int i = row + 1; i > 0; i -= i & (-i)) { //每次减去二进制形式最右侧的1for (int j = col + 1; j > 0; j -= j & (-j)) {sum += tree[i][j];}}return sum;}//更新操作//将(row,col)位置的值修改为val，可以修改为add来实现public void update(int row, int col, int val) { if (N == 0 || M == 0) {return;}int add = val - nums[row][col]; //增量 = 要修改成的值 - 原来的值nums[row][col] = val;//受影响的范围for (int i = row + 1; i <= N; i += i & (-i)) {for (int j = col + 1; j <= M; j += j & (-j)) {tree[i][j] += add;}}}//任意区域的累加和//计算 (row1,col1) 到 (row2, col2) 范围的值累加和public int sumRegion(int row1, int col1, int row2, int col2) {if (N == 0 || M == 0) {return 0;}return sum(row2, col2) + sum(row1 - 1, col1 - 1) - sum(row1 - 1, col2) - sum(row2, col1 - 1);}
}