# 前缀和算法

# 定义

前缀和，顾名思义，就是对一个数组的前一部分进行求和。最终会得到一个长度为 n+1 的数组，其中第 i 个元素表示原数组前 i 个元素的和。那么它有什么用呢？

前缀和算法可以用来快速计算一个区间的和。通过前缀和，我们可以把连续子数组的元素和转换成两个前缀和的差。

假设我们有一个数组 nums，前缀和数组为 preSum，那么 preSum[i] 表示 nums[0] 到 nums[i-1] 的和。我们可以通过 preSum[end+1] - preSum[start] 来计算 nums[start] 到 nums[end] 的和。

例如在[303] 区域和检索 - 数组不可变 中，我们可以使用前缀和来快速计算任意区间的和。我们只需要在初始化时计算出前缀和数组，然后在查询时通过前缀和数组来计算区间和，时间复杂度为 O(1)。

class NumArray {
  // 设 preSum 为前缀和
  preSum: number[];

  // 求前缀和
  init(nums: number[]): void {
    this.preSum = Array(nums.length + 1).fill(0);
    for (let i = 0; i < nums.length; i++) {
      this.preSum[i + 1] = this.preSum[i] + nums[i];
    }
  }

  // 查询区间和
  sumRange(left: number, right: number): number {
    return this.preSum[right + 1] - this.preSum[left];
  }
}

# 适用情况

前缀和算法一般常用与解决滑动窗口问题解决不了的数组区间题型。

例如在[560] 和为 K 的子数组中，我们可以使用前缀和来计算任意区间的和。我们可以用一个哈希表来存储前缀和的出现次数，然后遍历数组，计算当前前缀和与目标值的差值，如果差值在哈希表中存在，就说明找到了一个符合条件的子数组。

但这个问题却不能用滑动窗口的思路来解决。因为该题中数组允许出现负数，此时滑动窗口在收缩或扩展时，无法保证结果是单调的。例如收缩左侧窗口，其窗口中的和不一定会减小，如果去除的是负数结果会增大。

此时我们就更推荐用前缀和来解决这个问题。通过任意两前缀和的差值来计算区间和。

还有涉及到效率问题的一些情况。例如需要多次查询区间和。滑动窗口的时间复杂度是 O(n)，而前缀和的时间复杂度是 O(1)。如果我们需要多次查询区间和，那么前缀和会更高效。

# 扩展题型

如果是要求二维数组的前缀和呢？例如在[304] 二维区域和检索 - 矩形区域中，我们可以使用一个二维数组来存储前缀和。对于二维数组的前缀和，我们可以用 preSum[r][c] 表示从 (0, 0) 到 (r, c) 的矩形区域的和。我们可以通过 preSum[r2][c2] - preSum[r1-1][c2] - preSum[r2][c1-1] + preSum[r1-1][c1-1] 来计算任意矩形区域的和。

# 题型参考

[303] 区域和检索 - 数组不可变
[304] 二维区域和检索 - 矩形区域
[307] 区域和检索 - 数组可修改
[560] 和为 K 的子数组
[238] 除自身以外数组的乘积

← 滑动窗口算法