Range Sum Query - Immutable

题目地址：
https://leetcode.com/problems/range-sum-query-immutable/#/description

题目：

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:

Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

Note:

1. You may assume that the array does not change.
2. There are many calls to sumRange function.

解题思路：
这道题需要的是一个辅助array用来存储从index 0 到当前index的sum。这里有一个follow up，就是当是一个2D array的时候，给出两个坐标，然后求出坐标范围的sum。


代码：
follow up：

public class NumMatrix {
    int[][] sum;

    public NumMatrix(int[][] matrix) {
        if(matrix.length == 0 || matrix[0].length == 0){
            return;
        }
        sum = new int[matrix.length + 1][matrix[0].length + 1];
        for(int i = 0; i < matrix.length; i++){
            int temp = 0;
            for(int j = 0; j < matrix[0].length; j++){
                temp += matrix[i][j];
                sum[i + 1][j + 1] = sum[i][j + 1] + temp;
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        if(sum.length == 0){
            return 0;
        }
        return  sum[row2 + 1][col2 + 1] - sum[row2 + 1][col1] - sum[row1][col2 + 1] + sum[row1][col1];
    }
}