前缀和与差分一文搞懂：从一维到二维的区间操作降维打击

区间类问题是性能优化的常客：电商报表要反复查某段时间的销售额之和，游戏服务器要对一片区域批量加减状态，日志系统要统计任意窗口内的计数。这些操作朴素写法都是「查一次扫一遍」，查询频率一高就撑不住。前缀和与差分是处理这类问题的两个基本工具，而且互为逆运算——一个把「高频区间查询」压到 O(1)，一个把「高频区间更新」压到 O(1)，搞清楚各自适合的负载形态，区间问题的选型就基本定了。

这篇文章按「一维前缀和 → 一维差分 → 二维前缀和 → 二维差分」的顺序推进，每一步都交代推导与复杂度账目，代码全部给出可运行的 Python 实现，最后总结这对工具的适用边界与高频坑。

一维前缀和：预处理一次，查询 O(1)

前缀和的定义朴素到不像算法：prefix[i] 记录原数组前 i 个元素的总和，那么区间 [l, r] 的和就是 prefix[r+1] − prefix[l]。所有功夫花在预处理上，之后每次查询只做一次减法。实现上约定 prefix[0] = 0（空前缀），能让区间和公式免于「l 为零时要特判」的尴尬：

# 一维前缀和：区间和查询 O(1)（Python）
from itertools import accumulate

class PrefixSum:
    def __init__(self, nums: list[int]):
        # 前缀补 0：prefix[i] 表示前 i 个元素之和，查询公式无需特判
        self.prefix = [0] + list(accumulate(nums))

    def range_sum(self, left: int, right: int) -> int:
        """闭区间 [left, right] 的元素和，下标从 0 开始"""
        return self.prefix[right + 1] - self.prefix[left]

# 用法示例：nums = [3, 1, 4, 1, 5] 时，range_sum(1, 3) = 1 + 4 + 1 = 6

复杂度账目很清晰：预处理 O(n)、单次查询 O(1)、空间 O(n)。它的适用前提是数组内容在查询阶段不再修改——一旦存在频繁的单点更新，前缀和要连锁重算，单次更新退化到 O(n)。这正是选型的分水岭：只读数组、高频区间求和，用前缀和；更新频繁、查询稀少，用差分或线段树，别硬套。

一维差分：更新 O(1)，还原 O(n)

差分是前缀和的逆运算：diff[i] = nums[i] − nums[i−1]。它的魔力在于把「区间 [l, r] 整体加 v」翻译成两个点操作——diff[l] += v、diff[r+1] −= v，其余位置纹丝不动。所有区间更新完成后，对差分数组做一次前缀和还原，就得到最终数组。先看实现：

# 一维差分：区间批量加 O(1)（Python）
class DiffArray:
    def __init__(self, length: int):
        self.diff = [0] * (length + 1)  # 多留一位承接 r+1 的减操作

    def range_add(self, left: int, right: int, value: int) -> None:
        """把闭区间 [left, right] 内所有元素加 value"""
        self.diff[left] += value        # 区间起点：从这里开始生效
        self.diff[right + 1] -= value   # 区间终点后一位：从这里失效

    def build(self) -> list[int]:
        """对差分数组求前缀和，还原出更新后的完整数组"""
        result = []
        running = 0                     # running 即逐位累加的前缀和
        for delta in self.diff:
            running += delta
            result.append(running)
        return result[:-1]              # 末位是哨兵位，丢弃

# 用法示例：长度 6 的数组，对 [1, 4] 加 3、对 [2, 5] 减 1，
# 两次 range_add 后一次 build 还原，全程无逐元素循环。

为什么两个点操作能等价于一整段加法？因为差分数组的前缀和正是原数组：diff[l] += v 之后，从 l 开始的每个前缀和都多出 v，直到 r+1 处减回去——「生效区间的起点」与「失效的起点」两点定位，恰好刻画了任意区间。复杂度上单次更新 O(1)、最终还原 O(n)，适用于「先批量更新、最后统一取值」的场景；如果更新过程中还要随时读单点值，就必须在读取时维护增量累积，工具的边界就在这里。

二维前缀和：容斥原理登场

二维版本处理子矩阵和：给定矩阵，反复查询某个矩形区域内元素之和。设 P[i][j] 为以 (0,0) 与 (i−1,j−1) 为对角的子矩阵之和，任意子矩阵可由四个大前缀和拼出来——大矩形减掉左侧与上侧两个长条，减重复的区域要加回来，这就是容斥原理。推导写成公式：S(x1,y1,x2,y2) = P[x2+1][y2+1] − P[x1][y2+1] − P[x2+1][y1] + P[x1][y1]：

# 二维前缀和：子矩阵和 O(1) 查询（Python）
class PrefixSum2D:
    def __init__(self, matrix: list[list[int]]):
        rows, cols = len(matrix), len(matrix[0])
        # P 多一行一列全零，查询公式免去边界特判
        self.p = [[0] * (cols + 1) for _ in range(rows + 1)]
        for i in range(rows):
            for j in range(cols):
                # 当前行前缀 + 上方累计 - 左上重复区，得到到 (i,j) 的累计
                self.p[i + 1][j + 1] = (matrix[i][j]
                                        + self.p[i][j + 1]
                                        + self.p[i + 1][j]
                                        - self.p[i][j])

    def rect_sum(self, r1: int, c1: int, r2: int, c2: int) -> int:
        """闭区间行 [r1, r2]、列 [c1, c2] 的子矩阵和"""
        return (self.p[r2 + 1][c2 + 1]
                - self.p[r1][c2 + 1]        # 减去上方长条
                - self.p[r2 + 1][c1]        # 减去左侧长条
                + self.p[r1][c1])           # 加回被减两次的左上角

# 预处理 O(rows×cols)，单次查询 4 次下标访问，空间同预处理量级。

二维差分的思想完全同构，把「矩形区域整体加 v」变成四个角点的操作：左上加、右下角外加、右上外减、左下外减——正负号与前缀和的容斥方向恰好相反。还原时对差分矩阵做二维前缀和。掌握「一维到二维靠容斥」这条迁移路径后，甚至三维也只是多一层符号组合，思路不再新增。

适用边界与避坑总结

1. 先分清负载形态再选工具。只读数组 + 高频区间求和选前缀和；批量区间更新 + 最后统一读数选差分；更新与查询交错高频出现，两者都不合适，应该直接考虑线段树或树状数组——前缀和工具族解决的是「某一侧操作占绝对多数」的场景。
2. 下标偏移约定必须全篇一致。前缀和数组比原数组多一位、差分数组多留一个尾位，都是为了「右端点 +1 不越界」；这类代码最隐蔽的 bug 就是某处忘了偏移约定，导致答案整体错一位，写之前把 prefix 与原数组的下标关系在注释里钉死。
3. 二维容斥的加减顺序看区域包含关系，不要背符号。查询时大矩形减两个长条、加回重叠角；差分更新时符号方向相反。拿一个 2×2 的最小矩阵手算一遍所有角点的正负，比背诵公式可靠得多。
4. 差分适合区间整体操作，单点混用要重新设计。「区间加 v 之后立刻读某个点的值」这类交错负载，差分每次读取都要重新累积，等于变相 O(n)；遇到这种混合负载，及时升级到支持区间加与单点查的树状数组。
5. 前缀和可以与哈希结合解决「和为定值的子数组计数」。前缀和相减等于目标值即找到一段区间，用哈希表统计各前缀和出现次数，把这类「子数组和等于 k」问题降到 O(n)——这是前缀和最常见的变体考法，值得单独练熟。
6. 注意前缀和的溢出与精度。元素为整数且量级大时，Python 无忧但 C/Java 要用 long 承接累加；浮点数矩阵的前缀和会累积误差，对精度敏感的统计场景改用分段重算或双精度缓冲。

前缀和与差分是典型的「预处理换效率」思想，一维学会定义、二维学会容斥，整族工具就通了。它们与线段树不是竞争关系而是分工关系：负载单一时用它们最轻，负载交错时再升级重武器，选型意识比模板本身更值钱。

免责声明

本工具与文章内容仅用于学习测试场景，优化建议仅供参考，请勿直接用于生产环境，由此产生的风险自行承担。