前缀和

前缀和指一个数组的某下标之前的所有数组元素的和(包含其自身)。前缀和分为一维前缀和,以及二维前缀和。前缀和是一种重要的预处理,能够降低算法的时间复杂度。

前缀和、前缀积也称前缀和数组、前缀积数组。除了前缀和,还有后缀和、前缀积、后缀积

给一数组 A:

  1. 前缀和:新建一数组 B,数组中每一项 B[i] 保存 A[0...i] 的和;
  2. 后缀和:新建一数组 B,数组中每一项 B[i] 保存 A[i...n-1] 的和;
  3. 前缀积:新建一数组 B,数组中每一项 B[i] 保存 A[0...i] 的积;
  4. 后缀积:新建一数组 B,数组中每一项 B[i] 保存 A[i...n-1] 的积;

一维前缀和的公式:

sum[i] = sum[i - 1] + arr[i];

说明:

  • sum 是前缀和数组
  • arr 是内容数组

拥有前缀和数组后, 我们可以在 的时间复杂度内求出区间和。

[i, j] 的区间和公式:

interval[(i, j)] = sum[j] - sum[i - 1];

相关题目

  • 303 - 区域和检索 - 数组不可变(Easy)
  • 724 - 寻找枢纽元素(Easy)
  • 560 - 和为 K 的子数组(Medium)
  • 剑指 Offer II - 011 - 0 和 1 个数相同的子数组

参考资料