专题 13前缀和与差分

13.1前缀和：把区间和变成一次减法

先想一个生活场景：汽车里程表。你不需要每次都单独数「从 A 收费站到 B 收费站走了多远」——只要看 B 处的总里程减去 A 处的总里程就行。 里程表记录的，就是「从起点到当前位置的累计值」。前缀和就是这个思路搬到数组上。

定义与直觉

设数组 nums 长度为 n。我们定义前缀和数组 pre，其中

pre[i] = nums[0] + nums[1] + ... + nums[i-1]   // 即 nums[0..i-1] 的全部元素之和
pre[0] = 0   // 空区间的和为 0，作为哨兵

换句话说，pre[i] 记的是「下标 0 到 i-1」这段的累计和。注意它比 nums 多一位、且偏移一位——这是后面所有边界 bug 的根源，先记牢。

区间和如何变成一次减法

想求 nums[i..j]（含两端）的和。把它拆成「从开头到 j 的累计」减去「从开头到 i-1 的累计」：

nums[i] + nums[i+1] + ... + nums[j]
= (nums[0]+...+nums[j])        - (nums[0]+...+nums[i-1])
= pre[j+1]                     - pre[i]

所以任意区间和 = pre[j+1] - pre[i]，一次减法解决，与区间长度无关，是 O(1)。 暴力做法是每次从 i 加到 j，区间长度 m 就是 O(m)；前缀和把它降到 O(1)。当查询次数很多（比如力扣 303 允许多次调用）时，差距就从「超时」变成「轻松过」。

13.2一维前缀和模板

把上面思路落成一段可复用的代码。这是整个专题的基石，逐行读懂它，后面几题都是它的变体。

// 1) 构建前缀和（长度 n+1，pre[0]=0 哨兵，避免查询时判断 i==0 的特殊情况）
int n = nums.length;
int[] pre = new int[n + 1];
for (int i = 0; i < n; i++) {
    pre[i + 1] = pre[i] + nums[i];   // 递推：第 i+1 个前缀和 = 上一个 + 当前数
}

// 2) 查询区间 [l, r]（含两端，0-based）的和
int sum = pre[r + 1] - pre[l];       // 注意是 r+1 和 l，不是 r 和 l-1

为什么要「长度 n+1」且 pre[0]=0

如果 pre 和 nums 一样长（pre[i]=nums[0..i]），那么查询 [0, r] 时会用到 pre[-1]，下标为负要特判。 改成「偏移一位、pre[0]=0」后，区间 [l, r] 永远用 pre[r+1] - pre[l]，l=0 时只是减去 pre[0]=0，天然成立，无需任何特判。 这种「多开一位当哨兵」的技巧在数组题里反复出现，记住它省无数边界判断。

亲手走一遍：nums = [3, 1, 4, 1, 5, 9]

构建 pre（长度 7，pre[0]=0）：
  pre[0] = 0
  pre[1] = 0 + 3  = 3     (nums[0])
  pre[2] = 3 + 1  = 4     (nums[0..1])
  pre[3] = 4 + 4  = 8     (nums[0..2])
  pre[4] = 8 + 1  = 9
  pre[5] = 9 + 5  = 14
  pre[6] = 14 + 9 = 23

查询 [2, 4]（即 nums[2..4] = 4,1,5，期望 4+1+5=10）：
  pre[4+1] - pre[2] = pre[5] - pre[2] = 14 - 4 = 10  ✓

查询 [0, 0]（即 nums[0]=3）：
  pre[1] - pre[0] = 3 - 0 = 3  ✓ （l=0 时减去哨兵 0，无需特判）

可以看到，无论区间是否从头开始，公式 pre[r+1]-pre[l] 一律成立。这就是偏移设计的价值。

13.3区域和检索 - 数组不可变（简单，力扣 303）

简单 核心：前缀和最直接的应用——预处理一次，查询 O(1)

题意：给定一个整数数组 nums，实现一个类，支持多次调用 sumRange(i, j) 返回 nums[i..j] 的和（包含 i、j）。 例如 nums = [-2, 0, 3, -5, 2, -1]：

sumRange(0, 2) = (-2) + 0 + 3 = 1
sumRange(2, 5) = 3 + (-5) + 2 + (-1) = -1
sumRange(0, 5) = 全部之和 = -3

思路推导

题目的关键暗示在名字「数组不可变」——nums 建好之后不会改，但 sumRange 会被调用非常多次。 如果每次调用都从 i 加到 j，单次 O(n)，调用 m 次就是 O(m·n)，遇到海量查询必超时。

把问题套进 13.1 的框架：构造函数里一次性把前缀和 pre 建好（O(n)），之后每次查询只做一次减法（O(1)）。 这正是前缀和最 textbook 的用武之地——「查询远多于修改、且数据不变」时，预处理 + O(1) 查询是标准套路。

为什么不是用哈希？因为这题不是「找某个值」，而是「求一段连续和」，哈希帮不上忙，前缀和才是正解。两种武器分工明确：哈希管查找，前缀和管理区间累加。

参考代码

class NumArray {
    private int[] pre;   // pre[i] = nums[0..i-1] 的累加和，长度 n+1

    public NumArray(int[] nums) {
        int n = nums.length;
        pre = new int[n + 1];          // 多开一位，pre[0]=0 哨兵
        for (int i = 0; i < n; i++) {
            pre[i + 1] = pre[i] + nums[i];  // 递推构建：每个前缀和 = 上一个 + 当前元素
        }
    }

    public int sumRange(int i, int j) {
        // 下标 i..j 的和 = 前缀到 j 的累计 - 前缀到 i-1 的累计
        return pre[j + 1] - pre[i];
    }
}

复杂度：构造函数 O(n)（遍历建前缀和）；每次 sumRange O(1)（一次减法）。 空间 O(n)。之所以快，是因为「昂贵的累加」只发生一次，之后所有查询都「白嫖」这一次预处理的结果。

13.4和为 K 的子数组（中等，力扣 560）

中等 核心：前缀和 + 哈希计数，把「找子数组」变成「找出现过几次的目标前缀和」

题意：给定整数数组 nums 和整数 k，求和为 k 的连续子数组的个数。 例如 nums = [1, 1, 1]，k = 2，有 2 个满足条件的子数组：[1,1]（位置 0~1）和 [1,1]（位置 1~2），返回 2。

思路推导（从暴力到最优）

暴力：枚举所有起点 i、终点 j，算 nums[i..j] 的和是否等于 k。O(n²) 个子数组，每个再求和 O(n)，总 O(n³)；若边走边累加可降到 O(n²)，但 n 到 2×10⁴ 仍会超时。

前缀和观察：子数组 nums[i..j] 的和 = pre[j+1] - pre[i]。要它等于 k，即：

pre[j+1] - pre[i] == k
⇒  pre[i] == pre[j+1] - k

也就是说：以 j 结尾、和为 k 的子数组个数，等于「前面有多少个前缀和等于 pre[j+1] - k」。 暴力里我们是对每个 j 往前扫 i 去数；现在换思路——用哈希表记录「每个前缀和值出现过几次」，边走边查。

关键变形：不要去枚举 i，而是维护一个 Map<前缀和, 出现次数>。走到下标 x（当前前缀和记为 cur）时：

• 先问：cur - k 在哈希里出现过几次？那就是「以当前位置结尾、和为 k」的子数组个数，直接累加进答案。
• 再把 cur 自己记入哈希（次数 +1），供后面的位置查询。

为什么必须初始化 map.put(0, 1)？

这是本题最容易漏、漏了就错的一步。考虑子数组从下标 0 就开始的情况：比如 nums=[2], k=2。 走到 x=0，cur=2，我们要查 cur - k = 0 出现过几次。但此时哈希里还没有任何前缀和——除非我们一开始就把「前缀和 0（空前缀）」记成出现 1 次。

直觉：前缀和 pre[0]=0 代表「一个元素都没取」的空前缀。当一个子数组恰好从数组开头开始时，它的前缀和差里就用到这个 pre[0]=0。 不初始化，所有「从开头起、和为 k」的子数组都会被漏掉。所以开局 map.put(0, 1) 是必选项，不是可选项。

参考代码

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);            // 关键：空前缀和为 0，记 1 次，否则从下标 0 开始的子数组会被漏
        int cur = 0, ans = 0;     // cur：当前前缀和；ans：满足条件的子数组总数
        for (int x : nums) {
            cur += x;             // 走到当前位置的前缀和
            // 前面有多少个前缀和 == cur - k，就有多少个「以当前结尾、和为 k」的子数组
            ans += map.getOrDefault(cur - k, 0);
            // 把当前前缀和记入哈希，供后续位置查询
            map.put(cur, map.getOrDefault(cur, 0) + 1);
        }
        return ans;
    }
}

复杂度：时间 O(n)（一遍遍历，哈希增查均摊 O(1)）；空间 O(n)（哈希最坏存 n 个不同前缀和）。 对比暴力 O(n²)，这是质的飞跃——因为它把「对每个结尾往前数」换成了「一次哈希查表」。

亲手走一遍：nums = [1, 1, 1]，k = 2

map 初始 {0:1}，cur=0, ans=0
x=1: cur=1；查 cur-k = -1，map 里 0 次 → ans=0；map{0:1, 1:1}
x=1: cur=2；查 cur-k = 0，map 里 1 次 → ans=1；map{0:1,1:1,2:1}
x=1: cur=3；查 cur-k = 1，map 里 1 次 → ans=2；map{0:1,1:1,2:1,3:1}
返回 ans=2 ✓ （子数组 [0..1] 和 [1..2]）

注意第二次循环查到 cur-k=0 命中初始的 {0:1}——这正是「从开头到当前」那个子数组 nums[0..1] 被统计进来的原因。 如果没有 map.put(0,1)，这一步就查不到，答案会少 1。

13.5二维前缀和（中等，力扣 304）

中等 核心：一维前缀和升维，区间和靠「容斥原理」四个角相减

题意：给定一个二维矩阵 matrix，多次调用 sumRegion(row1, col1, row2, col2) 返回以 (row1,col1) 为左上、(row2,col2) 为右下的子矩阵元素和。 例如 matrix = [[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]，sumRegion(2,1,4,3) 返回 8。

思路推导：从一维到二维

一维时，区间和 = 两个端点的前缀和之差。二维时，「从 (0,0) 到 (i-1,j-1) 的矩形和」可以递推得到，关键还是「多包一圈」让下标从 1 开始，省去越界特判。

定义 pre[i][j] = 以 (0,0) 为左上、(i-1,j-1) 为右下的矩形和（i、j 从 1 起）。 构建时把当前格 matrix[i-1][j-1] 加进来，会重复计算两个半边，要用容斥修正：

pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + matrix[i-1][j-1]
            └ 上方矩形 ┘   └ 左方矩形 ┘   └ 重叠被加两次 ┘   └ 当前格 ┘

查询的容斥直觉（两块重叠面积）

想求子矩阵 (r1,c1) 到 (r2,c2) 的和。先取「从 (0,0) 到 (r2,c2) 的大矩形」pre[r2+1][c2+1]，它多包了上面和左边两块伸出部分：

            列 c1                       列 c2
行 r1  ┌─────────┬──────────────────────┐
       │ 左上伸出 │   我们要的目标矩形      │
       │ (要减)  │   (r1,c1)~(r2,c2)     │
行 r2  ├─────────┼──────────────────────┤
       │ 左下伸出 │  (这部分被多减，要加回) │
       └─────────┴──────────────────────┘

大矩形 pre[r2+1][c2+1] 减去「上方伸出」pre[r1][c2+1]、减去「左方伸出」pre[r2+1][c1]， 但左上角那块小矩形 pre[r1][c1] 被减了两次，要加回来一次：

答案 = pre[r2+1][c2+1] - pre[r1][c2+1] - pre[r2+1][c1] + pre[r1][c1]

记忆：「大减小减，左下角加回」，四块拼成一个减两加一。这是二维前缀和唯一容易写错的符号点（最后一个必须是 +）。

参考代码

class NumMatrix {
    private int[][] pre;   // pre[i][j]：从(0,0)到(i-1,j-1)的矩形和，i,j 从 1 起

    public NumMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        pre = new int[m + 1][n + 1];          // 多包一圈，pre[0][*]、pre[*][0] 全为 0
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 容斥递推：上方 + 左方 - 重叠 + 当前格
                pre[i][j] = pre[i - 1][j] + pre[i][j - 1]
                          - pre[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }
    }

    public int sumRegion(int r1, int c1, int r2, int c2) {
        // 大矩形 - 上伸 - 左伸 + 左上被多减的角
        return pre[r2 + 1][c2 + 1] - pre[r1][c2 + 1]
             - pre[r2 + 1][c1] + pre[r1][c1];
    }
}

复杂度：构建 O(m×n)（每个格算一次），每次查询 O(1)（四次加减）。空间 O(m×n)。 和一维一样，「昂贵的二维累加」只发生一次，海量查询稳过。

13.6差分：区间批量加减（中等，力扣 1094 拼车）

中等 核心：区间加减只需改两个端点，前缀和还原即实时值

题意：你有一辆车，容量 capacity。给定若干行程 trips[i] = [numPassengers, from, to]，表示在 from 站上 numPassengers 人，到 to 站下车（即人在 [from, to) 这段路上在车上）。 问能否在不超载的情况下完成所有行程。例如 trips = [[2,1,5],[3,3,7]]，capacity = 4：在位置 3~5 有 2+3=5 人 > 4，返回 false。

思路推导：从「区间加」到差分

朴素想法：建一个数组 cnt[位置] 表示每站车上人数，对每个 trip 把 [from, to) 每段都 +numPassengers。但这样每个 trip 可能改很多段，总 O(总里程)，数据大就慢。

差分的思想：「区间统一加一个数」其实不需要真的逐段加。我们维护一个差分数组 diff，只在两个端点做标记：

diff[from]      += numPassengers   // 在 from 站，上车，人数开始 +v
diff[to]        -= numPassengers   // 在 to 站，下车，人数结束（to 是开区间端点）

然后对 diff 求前缀和，就还原出每一站的实时人数：

cur = 0
for 每站 x:
    cur += diff[x]      // 前缀和 = 当前站车上实时人数
    if cur > capacity: 返回 false

上 / 下车的直觉对比

把 diff 想成「人数的变化量记录表」：有人上车，就在那站 +v；有人下车，就在那站 -v。 最后「累计变化」自然就是实时人数。这和前缀和正好是互逆操作：

为什么 diff[to] -= v 用开区间？因为 to 站人已经下车，to 这个位置本身不在车上。车上的区间是 [from, to)，所以在 to 这一格把人减掉，前缀和到 to 时人数正好回落。这正是里程表类比的反面：前缀和是「累计里程」，差分是「每段的里程增量」。

参考代码

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        int[] diff = new int[1001];   // 题目约定 from/to ≤ 1000，长度 1001 足够（to 最大 1000 仍合法）
        for (int[] t : trips) {
            int v = t[0], l = t[1], r = t[2];
            diff[l] += v;             // from 站上车：人数变化 +v
            diff[r] -= v;             // to 站下车：人数变化 -v（to 为开区间端点，人已不在车上）
        }
        int cur = 0;                  // 当前车上实时人数（diff 的前缀和）
        for (int x : diff) {
            cur += x;                 // 累加变化量 = 当前站人数
            if (cur > capacity) {     // 任一站超载，直接失败
                return false;
            }
        }
        return true;
    }
}

复杂度：时间 O(n + M)（n 为 trip 数，M 为位置范围上限，本题 M=1001）；空间 O(M)。 相比逐段加减，每个 trip 只动两个端点，效率极高。这正是差分「把区间操作压成端点操作」的威力。

13.7本专题常见坑

13.8自测题