「前缀和」指数组的某下标之前的所有数组元素和（包含其自身）。前缀和是一种重要的预处理，能够降低算法的时间复杂度。
const nums = [1,2,3,4,5,6,7,8,9]
现在需求来了，想获取「i」到「j」元素相加的和，如何求值？
const sumRange = (i, j) => { var sum = 0 for (let start = 0; i<j+1; i++){ sum += sums[i]; } return sum}
很简单，直接遍历嘛，通过下标拿到值后，相加即可；每次计算都需要检索一次，时间复杂度很高，我们应当想办法减少检索的次数。
链接：https://leetcode-cn.com/problems/range-sum-query-immutable/
var NumArray = function (nums) { const preSum = new Array(nums.length + 1) preSum[0] = 0 for (let i = 0; i < nums.length; i++) { preSum[i + 1] = preSum[i] + nums[i] } this.preSum = preSum};
NumArray.prototype.sumRange = function (left, right) { return this.preSum[right + 1] - this.preSum[left]};
第一次接触前缀和，一开始看的懵懵懂懂。看了一篇文章没看懂，然后又换另一个人文章看，在 leetcode 里看了三篇文章。终于有了眉目，前缀和的解法真不错呀。
如果我们能计算出数组在每个下标处的前缀和，那就可以降低每次调用 sumRange(i,j) 的时间复杂度。
具体的实现方法：想取「i」到「j」的和，需要存到另一个数组sums里，把「i」到「j」值相加，并且存进去，这样就有了一个「和」数组，当你想取「i」到「j」和时，就只需要用「和数组」的 sums[j + 1] – sums[i] 就行。
「前缀和」目的是新建一个数组 sums。把需要计算区间值的数组 nums，遍历它的 nums[i] + nums[i-1] 的值，存入数组 sums 中。
const nums = [1,2,3,4,5,6,7,8,9]
const sums = [0,1,3,6,10,15,21,28,36,45]
以后每次计算数值的时候，都操作的是 sums[j + 1] – sums[i]。
解决了每次求值都遍历的问题，其实前缀和经常用于对数组做预处理，在预处理阶段时间复杂度为O(n)，空间复杂度为O(n)，重要的是：后期的每次求值都是O(1)。
图片授权基于 www.pixabay.com 相关协议
其实前缀和经常用于对数组做预处理，将题目做等价转化成求 preSum 的问题
原创文章，作者：小道研究，如若转载，请注明出处：https://www.sudun.com/ask/34499.html
