题目：https://leetcode-cn.com/problems/range-sum-query-immutable/
解题思路一：遍历数组
传统的方法就是遍历数组，时间复杂度为 O(N)
class NumArray {
private int[] nums;
public NumArray(int[] nums) {
this.nums = nums;
}
public int sumRange(int left, int right) {
int sum = 0;
for (int i = left; i <= right; i++) {
sum += nums[i];
}
return sum;
}
}
这个比较简单，我们重点看下前缀和的解法。
解题思路二：使用前缀和技巧
首先根据传入的数组，计算一个新的数组，
新数组的每项为传入数组的前N个元素的和。
例如传入数组为 int[] nums = [1,3,-1,5,2]
那么新数组
第0项为：perSum[0] = 0 （固定让第0个元素为0,方便后面计算累加和)
第1项为：perSum[1] = 1即 int[1] = 1
第2项为：perSum[2] = 1+3，即int[2]=4
第3项为：perSum[3] = 1+3+(-1)，即int[2]=3
….
以此类推
第5项为：perSum[6] = 1+3+(-1)+5+2 即int[5]=10
所以从传入的数组 int[] nums = [1,3,-1,5,2] ，
我们得到一个新数组 int[] perSum =[0,1,4,3,8,10] 这个数组从第0项固定为0， 从第i(i>0)项开始，为nums 数组中从第0项到第i项的和。
得到新数组后，我们就可以通过简单的减法来计算传入的数组， 任意两个索引之间元素的和。
例如我想计算索引区间 [1,4]的元素的和，就可以通过 perSum[5]-perSum[1] 得出
注意：新数组的元素个数要比传入数组的元素多一个，因为新数组设置第0个元素为0 ，这是为了方便计算累加和
class NumArray {
private int[] perSum;
public NumArray(int[] nums) {
this.perSum = new int[nums.length +1];
for(int i = 1; i< this.perSum.length; i++ ){
perSum[i] = perSum[i-1] + nums[i-1];
}
}
public int sumRange(int left, int right) {
return perSum[right+1] - perSum[left];
}
}
这种技巧有点类似于高斯计算等差数列的和，有异曲同工之妙吧。
这种解法的时间复杂度是O(1)，因为不论有多少个数组元素，获取某个区间的和只是计算一次减法。
