前缀和数组

前缀和技巧
前缀和技巧适用于原始数组不会被修改的情况下，频繁地计算一个索引区间内的元素之和。
计算本质：某一段的区间和 = 起点到区间右端点的和（含右端点）- 起点到区间左端点的和（不含左端点）
一维前缀和
int[] nums;
int[] preSum = new int[nums.length + 1]; // Note
for(int i = 0; i < nums.length; i++){ preSum[i+1] = preSum[i] + nums[i]; } Note： 为减少一些边界处理，我们可以使前缀和数组下标从 1 开始记录，因此设定前缀和数组的长度为 n + 1。 preSum[0] 不必初始化为 0 （preSum[0] = 0;），因为在Note处，Java 创建前缀和数组会默认初始化为0。 preSum[i] = nums[0…i-1]的和 二维前缀和

前缀和数组最先出现在Python成神之路。