type NumMatrix struct {
	acc [][]int
}

func Constructor(matrix [][]int) (numMat NumMatrix) { // Constructor O(n^2), SumRegion O(1)
	rows := len(matrix)
	if rows == 0 {
		return
	}
	cols := len(matrix[0])
	numMat.acc = make([][]int, rows+1)
	for i := 0; i <= rows; i++ {
		numMat.acc[i] = make([]int, cols+1)
		for sum, j := 0, 1; i != 0 && j <= cols; j++ {
			sum += matrix[i-1][j-1] // sum is the sum of curr row
			numMat.acc[i][j] = sum + numMat.acc[i-1][j] // accumulate curr col
		}
	}
	return
}

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

/**
 * Your NumMatrix object will be instantiated and called as such:
 * obj := Constructor(matrix);
 * param_1 := obj.SumRegion(row1,col1,row2,col2);
 */