前缀和与差分详解

一句话总结

前缀和用于"频繁查询区间和"：预处理 O(n) 后，任意 [l, r] 的和都能 O(1) 算出。差分是它的逆运算，用于"频繁对区间做加减"：每次修改只需 O(1) 打两个标记，最后做一次前缀和还原。两者本质都是用预处理换查询速度。

📊

前缀和

pre[i] = 前 i 个数之和。sum(l, r) = pre[r+1] - pre[l]。

🏷️

差分

diff[l] += v, diff[r+1] -= v。还原后即为区间加 v 的结果。

🔲

二维前缀和

pre[i][j] 表示左上角矩形之和，容斥原理求子矩阵和。

🔑

前缀和 + 哈希表

把"和为 k 的子数组个数"从 O(n²) 降到 O(n)。

一、一维前缀和

1.1 构造与查询

class NumArray:
    def __init__(self, nums):
        self.pre = [0] * (len(nums) + 1)
        for i, x in enumerate(nums):
            self.pre[i + 1] = self.pre[i] + x       # 递推构造

    def sumRange(self, left, right):
        return self.pre[right + 1] - self.pre[left]   # O(1) 查询

# 更简洁的写法（Python）
from itertools import accumulate
pre = [0] + list(accumulate(nums))

💡 为什么 pre 长度是 n+1？为了让 left = 0 时公式 pre[right+1] - pre[left] 依然成立（此时需要 pre[0] = 0）。这个"哨兵位"是前缀和最容易写错的地方。

二、一维差分

2.1 核心思想

如果要对数组区间 [l, r] 里每个元素都加 v，朴素做法是 O(r-l+1)。差分数组只需两个 O(1) 操作：

def range_add(n, operations):
    # operations: [(l, r, v), ...] 表示对 [l, r] 每个元素 +v
    diff = [0] * (n + 1)
    for l, r, v in operations:
        diff[l] += v
        if r + 1 < n:
            diff[r + 1] -= v         # r+1 越界则不需要（已到末尾）

    # 对 diff 做前缀和还原
    res, cur = [], 0
    for i in range(n):
        cur += diff[i]
        res.append(cur)
    return res

# 经典题：1109 航班预订统计（每笔订单给区间 [i, j] 各加 seats 个座位）
def corpFlightBookings(bookings, n):
    diff = [0] * (n + 1)
    for first, last, seats in bookings:
        diff[first - 1] += seats          # 题目下标从 1 开始
        diff[last] -= seats
    for i in range(1, n):
        diff[i] += diff[i - 1]            # 就地做前缀和
    return diff[:n]

三、二维前缀和

3.1 容斥原理

class NumMatrix:
    def __init__(self, matrix):
        m, n = len(matrix), len(matrix[0])
        self.pre = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m):
            for j in range(n):
                self.pre[i + 1][j + 1] = (matrix[i][j]
                    + self.pre[i][j + 1]
                    + self.pre[i + 1][j]
                    - self.pre[i][j])

    def sumRegion(self, row1, col1, row2, col2):
        return (self.pre[row2 + 1][col2 + 1]
                - self.pre[row1][col2 + 1]
                - self.pre[row2 + 1][col1]
                + self.pre[row1][col1])

四、前缀和 + 哈希表：和为 K 的子数组

4.1 从 O(n²) 到 O(n)

560. 和为 K 的子数组。暴力枚举所有区间是 O(n²)。利用前缀和：区间 [j+1, i] 的和 = pre[i] - pre[j]。我们要它等于 K，即 pre[j] == pre[i] - K。于是遍历到 i 时，只需查"之前出现过多少次前缀和等于 pre[i] - K"。

from collections import defaultdict

def subarraySum(nums, k):
    count = defaultdict(int)
    count[0] = 1                      # ★ 关键：前缀和为 0 出现过 1 次（空前缀）
    pre = 0
    ans = 0
    for x in nums:
        pre += x                       # 当前前缀和
        ans += count[pre - k]          # 之前有多少个 pre[j] == pre - k
        count[pre] += 1               # 记录当前前缀和
    return ans
# 时间 O(n)，空间 O(n)

⚠️ 两个易错点：
① count[0] = 1 必须有——它代表"从第 0 个元素开始的子数组"这种情况；
② 必须先查询再插入。如果先 count[pre] += 1 再查 count[pre-k]，当 k=0 时会把自己也算进去，导致多算。

4.2 同类题目

题目	技巧
560 和为 K 的子数组	前缀和 + 哈希表计数
974 和可被 K 整除的子数组	记录 `pre % K` 的出现次数（注意负数取模）
523 连续的子数组和	同余定理 + 记录最早出现的余数下标
525 连续数组（0/1 相等）	把 0 当成 -1，转化为"和为 0 的最长子数组"
930 和相同的二元子数组	同上，计数版
1248 优美子数组	记录奇数个数的前缀计数

五、总结与选型

场景	工具	预处理	单次操作
静态数组，多次查区间和	前缀和	O(n)	O(1)
多次区间加减，最后一次性输出	差分	O(1) 每次	还原 O(n)
边修改边查询（动态）	线段树 / 树状数组	O(n)	O(log n)
矩阵多次查子矩阵和	二维前缀和	O(mn)	O(1)
矩阵多次子区域加减	二维差分	O(1) 每次	还原 O(mn)
求和为 K 的子数组个数	前缀和 + 哈希表	—	总 O(n)

一句话记住：前缀和是"差分"的逆，差分是"前缀和"的逆。查询多用前缀和，修改多用差分。两者结合（先差分打标记，再前缀和还原）能 O(n) 完成任意次区间加减。

与滑动窗口的关系：《滑动窗口》一篇中提到"有负数时不能滑动窗口求最短和 ≥ target"——那种情况的正确解法就是前缀和 + 单调队列 / 二分。前缀和不要求元素非负，是更通用的区间和工具。