阿聪的小破站algo›frame
前缀和算法详解
真的是，前面的回溯算法还没有看，这有来一个前缀和的算法，难受。
原文章地址：小而美的算法技巧：前缀和数组
简单理解，就是用前面已经算好的前缀加上当前元素的值作为当前元素的前缀和，比如nums = [2,3,5,1],
preSum = [2, ....]， 只算出来第一个值，这个时候要算第二个值的话，就可以用preSum[i-1] + nums[i]来计算。
class NumArray {
private int[] preSum;
public NumArray(int[] nums) {
preSum = new int[nums.length+1];
for(int i=1;i<preSum.length;i++){
preSum[i] = preSum[i-1] + nums[i-1]; // 为啥是i-1， 因为是从i开始的，方便计算总和
}
}
public int sumRange(int left, int right) {
return preSum[right+1] - preSum[left]; // 为什么是right+1?因为要取到right这个值， 为什么不去到left？因为要留下left对应的值
}
}