1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

// @Title: 二维区域和检索 - 矩阵不可变 (Range Sum Query 2D - Immutable)
// @Author: 15816537946@163.com
// @Date: 2022-03-20 17:54:14
// @Runtime: 728 ms
// @Memory: 16.4 MB
type NumMatrix struct {
	preSum [][]int
}

func Constructor(matrix [][]int) NumMatrix {
	var rows, cols int
	if len(matrix) == 0 {
		rows, cols = 1, 1
	} else {
		rows, cols = len(matrix)+1, len(matrix[0])+1
	}

	preSum := make([][]int, rows)
	for i := range preSum {
		preSum[i] = make([]int, cols)
	}

	for i := 0; i < rows; i++ {
		for j := 0; j < cols; j++ {
			if i == 0 || j == 0 {
				preSum[i][j] = 0
			} else {
				preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1] + matrix[i-1][j-1]
			}
		}
	}

	return NumMatrix{preSum: preSum}
}

func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
	return this.preSum[row2+1][col2+1] + this.preSum[row1][col1] - this.preSum[row1][col2+1] - this.preSum[row2+1][col1]
}