题目描述#

给定一个整数数组 nums，多次调用 sumRange(left, right)，返回下标 left 到 right（含两端）之间元素的和。数组本身不会被修改。

示例：

1
nums = [-2, 0, 3, -5, 2, -1]
2

3
sumRange(0, 2) → 1      // -2 + 0 + 3
4
sumRange(2, 5) → -1     // 3 + (-5) + 2 + (-1)
5
sumRange(0, 5) → -3     // 整个数组

约束： 0 <= nums.length <= 10^4，sumRange 最多调用 10^4 次。

朴素解为什么不给分#

每次 sumRange 都从 left 累加到 right，单次 O(n)。最坏情况下（每次查整个数组）总复杂度 O(n·q)，n = q = 10^4 就是 10⁸ 次累加——够呛，而且这个瓶颈每次查询都要重新付。

前缀和的价值就在「付一次，用很久」：构造时扫一遍 O(n)，之后每次查询只碰两次数组——O(1)。

关键：多开一位，语义才干净#

定义前缀数组 pre，长度 n + 1：

1
pre[0] = 0
2
pre[i] = nums[0] + nums[1] + ... + nums[i-1]     (1 ≤ i ≤ n)

也就是说 pre[i] 表示「前 i 个元素的和」，是一个左闭右开区间的累计值 [0, i)。多开的那一位 pre[0] = 0 是整套写法的粘合剂——它让「空区间」也有前缀和，边界不用特判。

于是区间 [left, right]（闭区间）的和可以写成两个前缀之差：

1
sum(left, right) = nums[left] + ... + nums[right]
2
                 = pre[right + 1] - pre[left]

为什么是 right + 1？因为 pre[right + 1] 才刚好包含到 nums[right]（前 right + 1 个元素 = 下标 0..right），而 pre[left] 恰好是 left 之前的部分。一头一尾对上了。

1
nums:  [ -2,  0,  3, -5,  2, -1 ]
2
index:    0   1   2   3   4   5
3

4
pre:   [ 0, -2, -2,  1, -4, -2, -3 ]
5
index:   0   1   2   3   4   5   6
6
          ↑                       ↑
7
      pre[0]=0             pre[6]=整个数组的和
8

9
sumRange(2, 5) = pre[6] - pre[2] = -3 - (-2) = -1   ✓
10
                  └ 前 6 个 ┘  └ 前 2 个 ┘

三段式模板#

前缀和的代码永远是三段：建表 → 查表 → （C 语言）释放。

1
① 建表：pre[0] = 0;  for i in 1..n:  pre[i] = pre[i-1] + nums[i-1]
2
② 查询：return pre[right + 1] - pre[left]
3
③ 释放：（C 语言）free 掉 pre 和对象本身

1
#include <stdlib.h>
2

3
typedef struct {
4
    int *pre;   /* pre[i] = nums[0..i-1] 的和，长度 n + 1 */
5
    int n;
6
} NumArray;
7

8
NumArray *numArrayCreate(int *nums, int numsSize) {
9
    NumArray *obj = (NumArray *)malloc(sizeof(NumArray));
10
    obj->n = numsSize;
11
    obj->pre = (int *)malloc((numsSize + 1) * sizeof(int));
12
    obj->pre[0] = 0;                                  /* 多开的一位 */
13
    for (int i = 0; i < numsSize; i++)
14
        obj->pre[i + 1] = obj->pre[i] + nums[i];      /* 前 i+1 个元素的和 */
15
    return obj;
16
}
17

18
int numArraySumRange(NumArray *obj, int left, int right) {
19
    return obj->pre[right + 1] - obj->pre[left];      /* 一头一尾 */
20
}
21

22
void numArrayFree(NumArray *obj) {
23
    free(obj->pre);
24
    free(obj);
25
}

1
#include <vector>
2
using namespace std;
3

4
class NumArray {
5
    vector<int> pre;   // pre[i] = nums[0..i-1] 的和，长度 n + 1
6
public:
7
    NumArray(vector<int>& nums) : pre(nums.size() + 1, 0) {
8
        for (int i = 0; i < (int)nums.size(); i++)
9
            pre[i + 1] = pre[i] + nums[i];             // 前 i+1 个元素的和
10
    }
11
    int sumRange(int left, int right) {
12
        return pre[right + 1] - pre[left];             // 一头一尾
13
    }
14
};

1
var NumArray = function (nums) {
2
  // pre[i] = nums[0..i-1] 的和，长度 n + 1
3
  this.pre = new Array(nums.length + 1).fill(0);
4
  for (let i = 0; i < nums.length; i++) {
5
    this.pre[i + 1] = this.pre[i] + nums[i]; // 前 i+1 个元素的和
6
  }
7
};
8

9
NumArray.prototype.sumRange = function (left, right) {
10
  return this.pre[right + 1] - this.pre[left]; // 一头一尾
11
};

复杂度#

易错点#

1. pre 忘记多开一位。 只开 n 长度，pre[right + 1] 在 right == n - 1 时就越界。多开的那一位不是「浪费」，它是 sumRange(0, x) 能写成统一公式的前提。
2. 下标差一。 记住这套语义就错不了：pre[i] 对应「前 i 个」，查询是 pre[right + 1] - pre[left]。right 要 +1、left 不要，是因为左闭右开区间 [left, right+1) 正好等于闭区间 [left, right]。
3. 混淆 nums[i] 和 pre[i] 的下标。 建表那行是 pre[i + 1] = pre[i] + nums[i]——pre 比 nums 整体错开一位。写成 pre[i] += nums[i] 就全乱了。
4. 题目没保证区间非空但保证了 left ≤ right。 left == right 时公式给出 nums[left] 本身，天然正确，不用特判。

题目描述#

给定一个二维矩阵 matrix，多次调用 sumRegion(row1, col1, row2, col2)，返回左上角 (row1, col1) 到右下角 (row2, col2) 构成的矩形区域内元素的和（四个角都含）。矩阵本身不会被修改。

示例：

1
matrix = [[3, 0, 1, 4, 2],
2
          [5, 6, 3, 2, 1],
3
          [1, 2, 0, 1, 5],
4
          [4, 1, 0, 1, 7],
5
          [1, 0, 3, 0, 5]]
6

7
sumRegion(2, 1, 4, 3) → 8     // 见下方矩形
8
sumRegion(1, 1, 2, 2) → 11
9
sumRegion(1, 2, 2, 4) → 12

约束： m, n <= 200，sumRegion 最多调用 10^4 次。

从一维到二维：多开「一圈」#

一维时多开一位（pre[0] = 0），二维时多开一行一列：pre 大小 (m + 1) × (n + 1)，第 0 行和第 0 列全填 0。

定义：

1
pre[i][j] = 矩阵中左上角 (0,0) 到右下角 (i-1, j-1) 的子矩阵之和

也就是 pre[i][j] 表示「前 i 行、前 j 列」构成的矩形和。多出来的第 0 行 / 第 0 列，就是二维版的 pre[0] = 0——它让「贴着上边界或左边界」的查询不用特判。

递推：一个格子由三个格子推出来#

pre[i][j] 覆盖的矩形，可以拆成三块已知区域再加当前格子 matrix[i-1][j-1]：

1
① pre[i-1][j]     正上方的矩形（前 i-1 行、前 j 列）
2
② pre[i][j-1]     正左方的矩形（前 i 行、前 j-1 列）
3
③ pre[i-1][j-1]   左上角重叠部分 —— 被 ①② 各算了一次，要减掉
4
④ matrix[i-1][j-1] 当前格子本身
5

6
pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + matrix[i-1][j-1]
7
            └────①────┘ └────②────┘ └─────③─────┘ └──────④──────┘

为什么减 pre[i-1][j-1]？ ① 和 ② 都覆盖了左上角那块「前 i-1 行、前 j-1 列」，它被重复加了两次，所以补一次减法——这就是容斥原理。

1
      前 j-1 列   第 j 列
2
    ┌──────────┬─────┐
3
前  ┌──────────┬─────┐
4
i-1 │    ③     │  ① │
5
行  ├──────────┼─────┤
6
第  │    ②     │  ④ │
7
i行 └──────────┴─────┘

查询：四个角，两个减一个加#

矩形 (r1, c1) ~ (r2, c2) 的和，用四个「从原点到某角」的前缀和做容斥：

1
sum(r1, c1, r2, c2)
2
  =   pre[r2 + 1][c2 + 1]     /* 大矩形：到右下角 */
3
    - pre[r1][c2 + 1]         /* 减：上方多出来的 */
4
    - pre[r2 + 1][c1]         /* 减：左方多出来的 */
5
    + pre[r1][c1]             /* 加：左上被减了两次，补回来 */

四个角的位置（注意每个都是 ±1 之后的前缀和下标）：

1
                        c1        c2
2
          0     c1        c2      c2+1
3
       ┌─────┬──────┬─────────┐
4
    0  │     │      │         │
5
       ├─────┼──────┼─────────┤
6
   r1  │     │  ▓▓  │  ▓▓▓▓▓  │   ← pre[r1][*]
7
       ├─────┼──────┼─────────┤
8
   r2  │     │  ▓▓  │  ▓▓▓▓▓  │   ← pre[r2+1][*]
9
       └─────┴──────┴─────────┘
10

11
   大矩形  pre[r2+1][c2+1]
12
 − 上方条  pre[r1][c2+1]
13
 − 左方条  pre[r2+1][c1]
14
 + 左上块  pre[r1][c1]      ← 被减两次，加回来
15
   ─────────────────────────
16
 = 目标    ▓▓ 格子之和

记忆口诀：右下 +1，左上不加；减两次的补一次加。 也就是 r2、c2 处取 +1，r1、c1 处原样，符号从左到右是 + − − +。

三段式模板#

1
#include <stdlib.h>
2

3
typedef struct {
4
    int **pre;         /* (m+1) x (n+1)，多开一圈 */
5
    int rows, cols;
6
} NumMatrix;
7

8
NumMatrix *numMatrixCreate(int **matrix, int matrixSize, int *matrixColSize) {
9
    int m = matrixSize, n = matrixColSize[0];
10
    NumMatrix *obj = (NumMatrix *)malloc(sizeof(NumMatrix));
11
    obj->rows = m;
12
    obj->cols = n;
13
    obj->pre = (int **)malloc((m + 1) * sizeof(int *));
14
    for (int i = 0; i <= m; i++)
15
        obj->pre[i] = (int *)calloc(n + 1, sizeof(int));   /* 多开的一圈，初值 0 */
16

17
    for (int i = 1; i <= m; i++)
18
        for (int j = 1; j <= n; j++)
19
            obj->pre[i][j] = obj->pre[i - 1][j] + obj->pre[i][j - 1]
20
                           - obj->pre[i - 1][j - 1] + matrix[i - 1][j - 1];
21
    return obj;
22
}
23

24
int numMatrixSumRegion(NumMatrix *obj, int row1, int col1, int row2, int col2) {
25
    return obj->pre[row2 + 1][col2 + 1]      /* 大矩形 */
26
         - obj->pre[row1][col2 + 1]          /* 减上方 */
27
         - obj->pre[row2 + 1][col1]          /* 减左方 */
28
         + obj->pre[row1][col1];             /* 补左上 */
29
}
30

31
void numMatrixFree(NumMatrix *obj) {
32
    for (int i = 0; i <= obj->rows; i++)
33
        free(obj->pre[i]);
34
    free(obj->pre);
35
    free(obj);
36
}

1
#include <vector>
2
using namespace std;
3

4
class NumMatrix {
5
    vector<vector<int>> pre;   // (m+1) x (n+1)，多开一圈
6
public:
7
    NumMatrix(vector<vector<int>>& matrix) {
8
        int m = matrix.size(), n = matrix[0].size();
9
        pre.assign(m + 1, vector<int>(n + 1, 0));
10
        for (int i = 1; i <= m; i++)
11
            for (int j = 1; j <= n; j++)
12
                pre[i][j] = pre[i - 1][j] + pre[i][j - 1]
13
                          - pre[i - 1][j - 1] + matrix[i - 1][j - 1];
14
    }
15
    int sumRegion(int row1, int col1, int row2, int col2) {
16
        return pre[row2 + 1][col2 + 1]   // 大矩形
17
             - pre[row1][col2 + 1]       // 减上方
18
             - pre[row2 + 1][col1]       // 减左方
19
             + pre[row1][col1];          // 补左上
20
    }
21
};

1
var NumMatrix = function (matrix) {
2
  const m = matrix.length;
3
  const n = matrix[0].length;
4
  // pre 是 (m+1) x (n+1)，多开的一圈是 0
5
  this.pre = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
6
  for (let i = 1; i <= m; i++) {
7
    for (let j = 1; j <= n; j++) {
8
      this.pre[i][j] =
9
        this.pre[i - 1][j] + this.pre[i][j - 1] - this.pre[i - 1][j - 1] + matrix[i - 1][j - 1];
10
    }
11
  }
12
};
13

14
NumMatrix.prototype.sumRegion = function (row1, col1, row2, col2) {
15
  return (
16
    this.pre[row2 + 1][col2 + 1] - // 大矩形
17
    this.pre[row1][col2 + 1] - // 减上方
18
    this.pre[row2 + 1][col1] + // 减左方
19
    this.pre[row1][col1] // 补左上
20
  );
21
};

复杂度#

易错点#

1. 四个角记混。 卡死时别背公式，回去看上面的容斥图：大矩形减上方条、减左方条，左上块被减了两次所以加回来。符号顺序 + − − +，只有 r2、c2 带 +1。
2. pre 的第 0 行 / 第 0 列没置 0。 C 语言里 malloc 不会清零——必须用 calloc（或 memset）把多开的一圈显式置 0，否则贴着上/左边界时读到垃圾值。
3. matrix[i-1][j-1] 写成了 matrix[i][j]。 建表循环从 1 开始，pre 的下标比 matrix 大 1，取原矩阵元素时一定要减回来。
4. 行列为空。 矩阵至少 1 行 1 列（题目约束保证），所以 C 版直接取 matrixColSize[0] 安全；但如果自己封装通用函数，空矩阵要单独挡一道。

局限 1：不支持动态修改#

前缀和是一次性算好、只读的结构。原数组只要改一个元素 nums[i]，从 i 往后所有的 pre[i] 全部失效，重建是 O(n)。

1
nums: [ 1, 2, 3, 4, 5 ]        把 nums[0] 改成 100
2
pre:  [ 0, 1, 3, 6, 10, 15 ]   →  pre[1..5] 全部要重算，O(n)

于是：

这就是题目为什么反复强调 “Immutable”——一旦可变，正确答案就不是前缀和了。树状数组和线段树本质上是「让前缀和也能增量更新」的升级版，那是另一个话题。

局限 2：只对「有逆运算」的运算成立#

一维取区间和的公式 pre[r+1] - pre[l]，本质是用减法去掉区间外的部分。所以前缀和只对有逆元的运算有效：

1
区间最小值 ≠ prefixMin[r+1] - prefixMin[l]     ← 完全错误，前缀 min 减不出来

需要区间 min / max / gcd 时，该换的武器是：

一句话判据：能写出 区间结果 = f(前缀, 前缀) 这种「相减/相消」关系的，才轮到前缀和。

局限 3：累加会溢出，也会丢精度#

前缀和是累加量，数值比原数组大得多，溢出风险和原数组不是一个量级。

• 整数溢出：10^5 个 10^9 级别的数相加，和能到 10^14——32 位 int 早就爆了。构建前缀和时必须开 long long（C / C++）/ BigInt（JS），哪怕题目原数组是 int。
• 浮点误差：pre[r+1] - pre[l] 是两个大数相减，大数相减会导致有效位丢失。若数组元素是浮点数，长前缀相减可能得到明显偏差的结果，需要对精度敏感的场景改用其他方案。
• 二维放大更快：矩阵不可变里 pre 的每个格子是矩形和，总量是 m·n 个元素的和——溢出门槛比一维更低，更要用宽类型。

1
// ❌ 原数组是 int，但前缀和一定是 long long
2
vector<int> pre(n + 1, 0);
3
pre[i + 1] = pre[i] + nums[i];          // 10^9 量级累加几万次就溢出
4

5
// ✅
6
vector<long long> pre(n + 1, 0);
7
pre[i + 1] = pre[i] + nums[i];

局限 4：丢掉了区间内部结构#

前缀和只记住「到某点的累计值」，换来 O(1) 查询，代价是看不见区间内部的分布。两类问题因此与它无缘：

• 需要内部极值的：区间最大值、最长连续子段……内部信息的答案没法由「两个前缀之差」推出（见局限 2）。
• 依赖单调性的：前缀和单调只在元素全非负时成立。数组里一旦有负数，pre 就不再单调，于是「二分前缀和找答案」这类套路当场失效——比如和为 K 的子数组，元素含负数时就不能靠双指针/二分，只能老老实实哈希表 + 前缀和统计出现次数（详见原理篇）。

1
nums = [1, -1, 1, -1]     pre = [0, 1, 0, 1, 0]   ← 上下反复，不单调
2
nums = [1,  2, 3,  4]     pre = [0, 1, 3, 6, 10]  ← 单调递增

局限小结#

记住前缀和的定位：它是「静态区间可逆聚合」的专用加速器，不是通用数据结构。 用之前先问三句——数据会变吗？运算可逆吗？数值会溢出吗？ 三问都过关，再上前缀和。