前缀和适合解决“多次查询固定数组的区间和”，差分适合解决“多次对数组区间进行相同修改”。它们的共同点是把批量操作转换为少量边界操作，再通过一次遍历恢复结果。

本文统一使用半开区间 [left, right)，并使用长度为 n + 1 的辅助数组处理边界，这样可以避免大量 left - 1 的特殊判断。

一、一维前缀和

1.1 定义

给定数组 nums，定义：

prefix[0] = 0
prefix[i + 1] = nums[0] + nums[1] + ... + nums[i]

于是区间 [left, right) 的和为：

prefix[right] - prefix[left]

1.2 Python 模板

def build_prefix(nums: list[int]) -> list[int]:
    prefix = [0] * (len(nums) + 1)
    for i, value in enumerate(nums):
        prefix[i + 1] = prefix[i] + value
    return prefix


def range_sum(prefix: list[int], left: int, right: int) -> int:
    """返回 nums[left:right] 的元素和。"""
    return prefix[right] - prefix[left]

构造前缀和的时间复杂度为 O(n)，每次区间查询的时间复杂度为 O(1)。

相关题目：1480. 一维数组的动态和、303. 区域和检索 - 数组不可变。

二、二维前缀和

2.1 定义

对于矩阵 matrix，定义：

prefix[i + 1][j + 1]

表示左上角为 (0, 0)、右下角为 (i, j) 的矩形区域和。

构造公式为：

prefix[i + 1][j + 1] =
    matrix[i][j]
    + prefix[i][j + 1]
    + prefix[i + 1][j]
    - prefix[i][j]

其中最后一项用于去除左上角区域被重复计算的部分。

2.2 Python 模板

def build_matrix_prefix(matrix: list[list[int]]) -> list[list[int]]:
    if not matrix or not matrix[0]:
        return [[0]]

    rows = len(matrix)
    cols = len(matrix[0])
    prefix = [[0] * (cols + 1) for _ in range(rows + 1)]

    for i in range(rows):
        for j in range(cols):
            prefix[i + 1][j + 1] = (
                matrix[i][j]
                + prefix[i][j + 1]
                + prefix[i + 1][j]
                - prefix[i][j]
            )

    return prefix


def matrix_sum(
    prefix: list[list[int]],
    top: int,
    left: int,
    bottom: int,
    right: int,
) -> int:
    """返回 matrix[top:bottom][left:right] 的元素和。"""
    return (
        prefix[bottom][right]
        - prefix[top][right]
        - prefix[bottom][left]
        + prefix[top][left]
    )

这里的 bottom 和 right 都是开区间边界。例如查询包含第 0 到第 2 行、第 1 到第 3 列的区域，应传入 (0, 1, 3, 4)。

相关题目：304. 二维区域和检索 - 矩阵不可变。

三、一维差分数组

3.1 定义

差分数组 diff 定义为：

diff[0] = nums[0]
diff[i] = nums[i] - nums[i - 1]  (i > 0)

对差分数组求前缀和，就可以恢复原数组。

3.2 区间增加

如果要让原数组的 [left, right) 区间全部增加 value，只需要修改两个边界：

diff[left] += value

最后对 diff 求一次前缀和，即可得到所有修改后的元素。

3.3 Python 模板

def apply_range_add(
    length: int, operations: list[tuple[int, int, int]]
) -> list[int]:
    """operations 中的区间均为 [left, right)。"""
    diff = [0] * (length + 1)

    for left, right, value in operations:
        diff[left] += value
        diff[right] -= value

    result = [0] * length
    current = 0
    for i in range(length):
        current += diff[i]
        result[i] = current

    return result

每次区间修改的时间复杂度为 O(1)，全部修改完成后恢复数组的时间复杂度为 O(n)。

相关题目：1109. 航班预订统计。题目使用闭区间和从 1 开始的编号，套用模板时需要先转换为半开区间和从 0 开始的下标。

四、二维差分数组

4.1 区域增加的四个边界

对于矩阵的半开区域 [top, bottom) × [left, right) 增加 value，修改二维差分数组的四个位置：

diff[top][left] += value

这四次修改通过二维前缀和抵消矩形外的影响，只保留目标区域。

4.2 Python 模板

def apply_matrix_range_add(
    rows: int,
    cols: int,
    operations: list[tuple[int, int, int, int, int]],
) -> list[list[int]]:
    """operation 格式为 (top, left, bottom, right, value)。"""
    diff = [[0] * (cols + 1) for _ in range(rows + 1)]

    for top, left, bottom, right, value in operations:
        diff[top][left] += value
        diff[bottom][left] -= value
        diff[top][right] -= value
        diff[bottom][right] += value

    result = [[0] * cols for _ in range(rows)]
    for i in range(rows):
        for j in range(cols):
            top = result[i - 1][j] if i > 0 else 0
            left = result[i][j - 1] if j > 0 else 0
            diagonal = result[i - 1][j - 1] if i > 0 and j > 0 else 0
            result[i][j] = top + left - diagonal + diff[i][j]

    return result

相关题目：2536. 子矩阵元素加 1。

五、如何选择

问题类型 适合的方法 单次操作复杂度
固定数组，多次查询区间和 前缀和 O(1) 查询
多次对数组区间增加相同值 一维差分 O(1) 修改
固定矩阵，多次查询子矩阵和 二维前缀和 O(1) 查询
多次对矩阵区域增加相同值 二维差分 O(1) 修改

如果查询和修改操作需要交替进行，静态前缀和或差分数组通常不再适用，此时可以考虑树状数组或线段树。

六、总结

  • 前缀和把区间求和转换为两个前缀值的减法。
  • 差分数组把区间修改转换为边界上的常数次修改。
  • 使用长度为 n + 1 的辅助数组，可以统一处理数组边界。
  • 一维和二维的思想相同，二维公式需要额外减去重复计算的左上区域。