什么是前缀和（2389）
前缀和指一个数组的某下标之前的所有数组元素的和（包含其自身）。前缀和分为一维前缀和，以及二维前缀和。前缀和是一种重要的预处理，能够降低算法的时间复杂度。
什么是一维前缀和？
一维前缀和的公式：sum[i] = sum[i-1] + arr[i] ; sum是前缀和数组, arr是内容数组。拥有前缀和数组后, 我们可以在O(1)的时间复杂度内求出区间和。
[i, j]的区间和公式: interval [i, j] = sum[j] - sum[i - 1]
作者：dyhtps
链接：https://juejin.cn/post/6944913393627168798
来源：稀土掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。