【模板】前缀和与差分

摘要: 介绍关于前缀和与差分的算法原理，并实现力扣 303、304 这两个模板题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

各位好，本文我来看一下前缀和与差分，这是一个基础算法，大学的算法和数据结构一般不会讲，但是刷题的时候会发现大量题目都跟他有关，在力扣上可以找到 100 多道相关题目，以前写过相关的题目汇总，可以参考 前缀和问题分类汇总。

本文详细梳理以下前缀和与差分的算法原理，代码模板，以及常见的用法。并顺便实现力扣 303、304 这两个模板题。主要内容如下：

• 一维和二维前缀和模板
• 前缀和和差分的常见套路

---

$1 一维前缀和

模板题

• 303. 区域和检索 - 数组不可变

给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。

1. 你可以假设数组不可变。
2. 会多次调用 sumRange 方法。

样例：
给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

前缀和算法

给定长度 n 的序列 $a_{0}, a_{1}, …, a_{n-1}$ , 给每个前缀求一次和，具体定义如下：

$$S_{0} = 0$$ $$S_{i}=\sum\limits^{i-1}\limits_{j=0}a_{j}$$

这些前缀和维护在一个长度 n + 1 数组 S 里。之后 S 数组可以支持 O(1) 求区间 [i, j] 的和，答案是 S[j+1] - S[i], 其中 0 <= i <= j <= n - 1。

建 S 数组的过程需要额外 O(n) 空间，和总共 O(n), 摊销 O(1) 的时间。

代码(C++) 一维前缀和

class NumArray {
public:
    NumArray(vector<int>& nums) {
        if(nums.empty())
            sums = vector<int>();
        else
        {
            int n = nums.size();
            sums = vector<int>(n + 1, 0);
            for(int i = 1; i <= n; ++i)
                sums[i] = sums[i - 1] + nums[i - 1];
        }
    }

    int sumRange(int i, int j) {
        // 0 <= i <= j <= n-1
        if(sums.empty()) return 0;
        return sums[j + 1] - sums[i];
    }

private:
    vector<int> sums;
};

代码(Python) 一维前缀和

class NumArray:
    def __init__(self, nums: List[int]):
        n = len(nums)
        self.sums = [0] * (n + 1)
        for i in range(n):
            self.sums [i + 1] = self.sums[i] + nums[i]

    def sumRange(self, left: int, right: int) -> int:
        return self.sums[right + 1] - self.sums[left]

---

$2 二维前缀和

模板题

• 304. 二维区域和检索 - 矩阵不可变

给定一个二维矩阵 matrix，以下类型的多个请求：

• 计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。

实现 NumMatrix 类：

• NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
• int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素 总和 。

示例 1：
输入:
[“NumMatrix”,”sumRegion”,”sumRegion”,”sumRegion”]
[[[[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]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
输出:
[null, 8, 11, 12]
解释:
NumMatrix numMatrix = new NumMatrix([[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]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)

前缀和算法

题目是前面的 303 题二维的版本，前缀和算法也相应地变为二维前缀和算法。

在二维的情况下，前缀和的含义是从某个点到左上角点之间的矩形范围内的所有元素的和。

算法的流程依然是先求出每个元素的前缀和，然后在进行区域和的查询时，直接使用已经算好的前缀和计算后得到答案。

只是计算前缀和以及计算查询的区域和的过程比一维复杂一些，需要用到容斥原理。类似于一维前缀和，二维前缀和定义如下：

$$S[0][y] = S[x][0] = 0$$ $$S[x][y] = \sum\limits_{i=0}\limits^{x-1}\sum\limits_{j=0}\limits^{y-1}a[i][j]$$

在求前缀和的过程中，假设求到了 a[x][y]，它对应的前缀和是 sums[x+1][y+1]，此时 sums[x][y+1], sums[x+1][y], sums[x][y] 的前缀和已经求出来了。使用容斥原理计算当前 (x, y) 的前缀和的公式如下：

sums[x + 1][y + 1] = sums[x][y + 1] + sums[x + 1][y] - sums[x][y] + a[x][y]

建好 sums 数组之后求两个点之间的矩形区域和时也需要借助容斥原理。例如要求 (x1, y1), (x2, y2) 之间的区域和，如下图：

我们已有的是 sums[x1][y1]、sums[x1][y2 + 1]、sums[x2 + 1][y1]、sums[x2 + 1][y2 + 1]，观察图中这四个前缀和的关系，区域和的计算公式如下

sums[x2 + 1][y2 + 1] - sums[x2 + 1][y1] - sums[x1][y2 + 1] + sums[x1][y1])

代码(C++) 二维前缀和

class NumMatrix {
public:
    NumMatrix(vector<vector<int>>& matrix) {
        if(matrix.empty())
            sums = vector<vector<int> >();
        else
        {
            int m = matrix.size();
            int n = matrix[0].size();
            sums = vector<vector<int> >(m + 1, vector<int>(n + 1, 0));
            for(int i = 1; i <= m; ++i)
                for(int j = 1; j <= n; ++j)
                    sums[i][j] = sums[i][j - 1] + sums[i - 1][j]
                        - sums[i - 1][j - 1] + matrix[i - 1][j - 1];
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        if(sums.empty()) return -1;
        // row1 <= row2, col1 <= col2
        return sums[row2 + 1][col2 + 1] - sums[row2 + 1][col1]
            - sums[row1][col2 + 1] + sums[row1][col1];
    }

private:
    vector<vector<int> > sums;
};

代码(Python) 二维前缀和

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

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return int(self.sums[row2 + 1][col2 + 1] - self.sums[row2 + 1][col1] \
                - self.sums[row1][col2 + 1] + self.sums[row1][col1])

---

$3 前缀和算法的扩展

能推广的运算

满足区间减法的运算，区间 A = [i, j], 区间 B = [i, k] 区间 C = [k+1, j]，那么有了大区间 A 上的结果 a 和其中一个小区间 B 上的结果 b, 要能够算出另一个小区间 C 上的结果 c。

异或: $a = b \oplus c \Leftarrow c = b \oplus a$

乘法/模下乘法: $a = b \times c \Leftarrow c = a / b$

前缀和 + 数据结构

将前缀和维护在数据结构中，以便于后续的多次查询，最常见的是维护在哈希表中。

经典一问：$a_{0}, a_{1}, …, a_{n-1}$ 上有没有一个区间，其和为 target。 这一问就是题目 560. 和为K的子数组

当扫描到 i 时， $a_{0}, a_{1}, …, a_{i-1}$ 的前缀和都已经求过了，把它们维护到 unordered_set 中，求完当前值 a[i] 对应的前缀和 S[i+1], 在插入到 unordered_set 之前先问：S[i+1] - target 在 unordered_set 中是否出现，如果出现则找到答案。

上面的问题还可以有变种：

• 第1问：$a_{0}, a_{1}, …, a_{n-1}$ 上有多少个区间，其和为 target。

答案是把 unordered_set 改成 unordered_map 就可以。

• 第2问：$a_{0}, a_{1}, …, a_{n-1}$ 上有没有一个区间，其和大于/小于 target。这一问就是题目 327. 区间和的个数

答案是把 unordered_set 改成线段树。

• 第3问: 第一问的树形版本，也就是题目 437. 路径总和 III

答案是dfs(前序遍历)时，栈里存的是当前节点到根的链，这条链上的和可以作为前缀和维护在 unordered_map 里。从左子树跳到右子树的时候，左子树的所有节点对应的前缀和要先从 unordered_map 中删掉。

差分

前缀和序列 $S_{0}, S_{1}, …, S_{n}$ 的差分序列 $a_{0}, a_{1}, …, a_{n-1}$ 就等于原序列，其中 $a_{i} = S_{i+1} - S_{i}$ 。

原序列 $a_{0}, a_{1}, …, a_{n-1}$ 的差分序列为 $b_{0}, b_{1}, …, b_{n-1}$ ，其中 $b_{0} = a_{0} - 0, b_{i} = a_{i} - a_{i-1}$ 。则对差分序列求前缀和序列，就得到原序列。

差分序列的好处是如果要对原序列的一个区间 [l, r] 上所有值加 val，原序列上要操作 r-l+1 次(a[l .. r] + val)，在差分序列上只需要操作 2 次(b[l] + val, b[r+1] - val)。如果这种区间操作需要很多次，最后的查询只有一次的话，就非常适合在差分序列上操作。

用差分维护区间加法的模板题：370. 区间加法

---