308.範囲合計クエリ2D-可変



308 Range Sum Query 2d Mutable



説明

2D行列行列が与えられた場合、左上隅(row1、col1)と右下隅(row2、col2)で定義される長方形内の要素の合計を求めます。

範囲合計クエリ2D
上記の長方形(赤い境界線付き)は、(row1、col1)=(2、1)および(row2、col2)=(4、3)で定義され、合計= 8が含まれます。



例:
与えられた行列= [
[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]
]

sumRegion(2、1、4、3)-> 8
update(3、2、2)
sumRegion(2、1、4、3)-> 10
注意:
マトリックスは、更新機能によってのみ変更可能です。
updateおよびsumRegion関数の呼び出し数が均等に分散されていると想定できます。
row1≤row2およびcol1≤col2であると想定できます。



問題のURL


解決

2次元配列の場合、囲まれた長方形内のすべての数値の合計を計算できる必要があります。

これまで、この列の合計を含む2次元配列を維持します。更新するときは、差を数えて、この列の末尾に適用します。検索するときは、結果を列ごとに数えます。



コード

class NumMatrix { private int[][] matrix private int[][] colSums public NumMatrix(int[][] matrix) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0){ return } this.matrix = matrix int m = matrix.length, n = matrix[0].length colSums = new int[m + 1][n] for (int i = 1 i <= m i++){ for (int j = 0 j < n j++){ colSums[i][j] = colSums[i - 1][j] + matrix[i - 1][j] } } } 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 < colSums.length i++){ colSums[i][col] += diff } } public int sumRegion(int row1, int col1, int row2, int col2) { int res = 0 for (int i = col1 i <= col2 i++){ res += (colSums[row2 + 1][i] - colSums[row1][i]) } return res } } /** * 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) */

時間計算量:O(n)
スペースの複雑さ:O(n ^ 2)


レビュー