共计 1738 个字符，预计需要花费 5 分钟才能阅读完成。
数组的前缀和技巧，是通过“空间换时间”的策略，它通过预先求得数组前 [x,y] 项 元素的和 并存入 arr[x,y] = sum
前缀和的数组，其每一项的值是 数组前 n 项 数据的和，比如第 n 项 preSum[n] = 前 n-1 所有项元素的和
这个方法针对 一些 要求数组某个区间的和的题目，会使得时间复杂度降为 O(1)。
先看一个题目：
给你一个矩阵 matrix，计算索引
left和right（包含left和right）之间的nums元素的 和 ，其中left <= right
如果，在没学过前缀和以前，可能的实现过程是这样的：
public int sumRange(int left, int right) {
// 用 for 循环遍历求和
int sum = 0;
for (int i = left; i <= right; i++) {sum += nums[i];
}
return sum;
}此时要求得范围内 元素的和，时间复杂度为 O(n) 而且这个方法在使用频繁的情况下，效率更糟糕
一维的前缀和实现方法
/**
* @param {number[]} nums
*/
var NumArray = function(nums) {if(nums.lengt === 0 && typeof nums === null) {return []
}
let preSum = new Array(nums.length + 1).fill(0)
preSum[0] = 0
// 此处预先将和求得以后存入数组的每项
for(let i =1;i < preSum.length; i++) {preSum[i] = preSum[i -1] + nums[i - 1]
}
this.preSum = preSum
};
/**
* @param {number} left
* @param {number} right
* @return {number}
*/
NumArray.prototype.sumRange = function(left, right) {
// 直接计算 求得范围内 元素的和
return this.preSum[right + 1] - this.preSum[left]
};
要搞明白这个前缀和，就从这段代码说起
let preSum = new Array(nums.length + 1).fill(0)
preSum[0] = 0
// 此处预先将和求得以后存入数组的每项
for(let i =1;i < preSum.length; i++) {preSum[i] = preSum[i -1] + nums[i - 1]
}
this.preSum = preSum
};这段代码，首先初始化了一个一维的数组 它的长度是给定的数组的长度 +1
将它的第一个元素设置为 0，是便于后续的计算。
着重看一下 循环体的实现：
for(let i =1;i < preSum.length; i++) {
preSum[i] = preSum[i -1] + nums[i – 1]
}
这段代码，初始化一个循环变量 i，从 1 开始作为访问数组的索引，循环体：preSum[i] = preSum[i -1] + nums[i – 1] 表示，当前数组位置保存前一个数组位 + 给定的数组的当前位。实际上 设置 preSum[0] = 0，正是为了将给定数组的第一位的值存进去，后续的循环天然形成了一种：preSum 数组 保存的值永远是其前一项值 加上给定数组的最新的一项的值。
就好像是这样一个感受：给定数组在上面洒水，而我们的数组在下面接。所以我们的数组保存的值一直是滞后的，而给定数组的值永远是相比而言往前一项。那么，在每一次循环就是一次递增，每一项正好是前面的前面的和 + 前面的一项，所以当前项 preSum[n] 的值 就是前 n - 1 项 所有元素的和
注意点：
在了解前缀和的实现原理之后，对于使用它，是有一些局限的
- 使用前缀和，原给定数组的值 不应该发生变化，不然，我们已经计算过的和 都会失效。这样情况下，再重新计算和，则会花费更多的时间，失去了其存在的意义
用豆包的话说：前缀和数组是基于原数组的“累加结果”构建的，一旦原数组元素发生修改（如增、删、改），前缀和数组会产生“连锁反应”，导致更新效率极低。
2. 极端情况下，复杂度显著上升
当维度上升到二维，三维，这种用空间换时间的 技巧，其收益率大幅下降。因为需要维护前缀和数组，若原数组还需保留，那么空间需求更大
3. 该技巧只支持累加类的题目，除此之外 该技巧很可能失效。
