二维前缀和&二维差分（超详细，python版，其他语言也很轻松能看懂）-Toy模板网

这篇具有很好参考价值的文章主要介绍了二维前缀和&二维差分（超详细，python版，其他语言也很轻松能看懂）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

上一篇文章讲解了一维前缀和&一维差分，本篇进阶为二维。

二维前缀和：

二维前缀和跟一维前缀和求法相同，这里直接上例子。
数组a = [[1,2,2,1],[3,2,2,1],[1,1,1,1]]

a数组如图：
二维差分python,python,算法,算法,python,蓝桥杯

则数组a的前缀和为：数组b[[1,3,5,6],[4,8,12,14],[5,10,15,18]]

b数组如图：
二维差分python,python,算法,算法,python,蓝桥杯
前缀和递推公式为 b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + a[i][j]，因为i = 0 和 j = 0时，会超出索引范围，所以在定义数组a,b时应该多定义一行0和一列0，如图所示a数组

二维差分python,python,算法,算法,python,蓝桥杯
这样就不会报错，也不需要进行首行和首列的单独定义，更加方便理解和书写。

二维差分：

前文中讲到类似于数学中的求导和积分，差分可以看成前缀和的逆运算。
像上述数组a,b 数组a就是数组b的差分数组。

这里以模板题为准，讲解两种差分方法，一种便于理解，一种就是优化，稍微难理解点，建议大家掌握第一种方法（第二种方法我理解半天才搞懂。。。）先看题。

差分矩阵：

题目链接：差分矩阵
输入一个 n 行 m 列的整数矩阵，再输入 q 个操作，每个操作包含五个整数 x1,y1,x2,y2,c，其中 (x1,y1) 和 (x2,y2) 表示一个子矩阵的左上角坐标和右下角坐标。每个操作都要将选中的子矩阵中的每个元素的值加上 c。
请你将进行完所有操作后的矩阵输出。

输入格式
第一行包含整数 n,m,q。接下来 n 行，每行包含 m 个整数，表示整数矩阵。接下来 q 行，每行包含 5 个整数 x1,y1,x2,y2,c，表示一个操作。

输出格式
共 n 行，每行 m 个整数，表示所有操作进行完毕后的最终矩阵。

数据范围
1≤n,m≤1000,
1≤q≤100000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,
−1000≤c≤1000,
−1000≤矩阵内元素的值≤1000

输入样例：

3 4 3
1 2 2 1
3 2 2 1
1 1 1 1
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1

输出样例：

2 3 4 1
4 3 4 1
2 2 2 2

方法一（很好理解）：

因为差分可以看成前缀和的逆运算，可以从矩阵前缀和的构造中反推出差分矩阵。

二维前缀和的递推公式为b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + a[i][j]

这里b是前缀和矩阵，a是差分矩阵。

所以可以反推出a[i][j] = b[i][j] - b[i - 1][j] - b[i][j - 1] + b[i - 1][j - 1]

递推公式有了就可以构造差分矩阵，为了方便理解和书写，定义矩阵时要多定义一行和一列（差分数组要多定义两行两列，之后区间加减数时会用到，使之不超出索引范围）

差分矩阵有了，如何加减呢？
与一维差分类似，这里给出差分数组的区间图方便大家理解，给出x1,y1,x2,y2,c，要在b[x1][y1] ~ b[x2][y2] 内加c

如图所示：
二维差分python,python,算法,算法,python,蓝桥杯
b[x1][ y1 ] +=c ; 对应下图1 ,让整个a数组中蓝色矩形面积的元素都加上了c。
b[x1,][y2+1]-=c ; 对应图2 ,让整个a数组中绿色矩形面积的元素再减去c，使其内元素不发生改变。
b[x2+1][y1] -=c ; 对应图3 ,让整个a数组中紫色矩形面积的元素再减去c，使其内元素不发生改变。
b[x2+1][y2+1] +=c; 对应图4,让整个a数组中红色矩形面积的元素再加上c，红色内的相当于被减了两次，再加上一次c，才能使其恢复。

二维差分python,python,算法,算法,python,蓝桥杯
这样，我们构造二维差分数组让原二维数组a中所选中子矩阵中的每一个元素加上c的操作，可以由O(n*n)的时间复杂度优化成O(1)（四次操作）。

之后就用前缀和公式求出新的前缀和矩阵是什么即可。

方法二（优化）：

方法二的优化其实也没有优化多少，而且不太好理解，不是很推荐，但毕竟多多少少还是有可取之处。

a[][]数组是b[][]数组的前缀和数组，那么b[][]是a[][]的差分数组

原数组： a[i][j]

我们去构造差分数组： b[i][j]

使得a数组中a[i][j]是b数组左上角(1,1)到右下角(i,j)所包围矩形元素的和。

如何构造b数组呢？

我们去逆向思考。

同一维差分，我们构造二维差分数组目的是为了让原二维数组a中所选中子矩阵中的每一个元素加上c的操作，可以由O(n*n)的时间复杂度优化成O(1)

已知原数组a中被选中的子矩阵为以(x1,y1)为左上角，以(x2,y2)为右下角所围成的矩形区域;

始终要记得，a数组是b数组的前缀和数组，比如对b数组的b[i][j]的修改，会影响到a数组中从a[i][j]及往后的每一个数。

假定我们已经构造好了b数组，类比一维差分，我们执行以下操作
来使被选中的子矩阵中的每个元素的值加上c

b[x1][y1] += c;

b[x1][y2+1] -= c;

b[x2+1][y1] -= c;

b[x2+1][y2+1] += c;

每次对b数组执行以上操作，等价于：
a[i][j]+=c；

我们画个图去理解一下这个过程：
二维差分python,python,算法,算法,python,蓝桥杯

b[x1][ y1 ] +=c ; 对应图1 ,让整个a数组中蓝色矩形面积的元素都加上了c。
b[x1,][y2+1]-=c ; 对应图2 ,让整个a数组中绿色矩形面积的元素再减去c，使其内元素不发生改变。
b[x2+1][y1]- =c ; 对应图3 ,让整个a数组中紫色矩形面积的元素再减去c，使其内元素不发生改变。
b[x2+1][y2+1]+=c; 对应图4,让整个a数组中红色矩形面积的元素再加上c，红色内的相当于被减了两次，再加上一次c，才能使其恢复。

二维差分python,python,算法,算法,python,蓝桥杯

方法二的重点就在这，前面一堆废话

我们可以先假想a数组为空，那么b数组一开始也为空，但是实际上a数组并不为空，因此我们每次让b数组以(i,j)为左上角到以(i,j)为右下角面积内元素(其实就是一个小方格的面积)去插入 c=a[i][j]，等价于原数组a中(i,j) 到(i,j)范围内加上了 a[i][j] ,因此执行n*m次插入操作，就成功构建了差分b数组.

这叫做曲线救国。

代码及详细注释：

n, m, c = map(int, input().split())  # 输入三个整数n, m, c

# 初始化二维列表a，将第一行全为0，后续行根据输入的路径更新
a = [[0] * (m + 1)]
for i in range(n):
    path = list(map(int, input().split()))
    path = [0, *path]  # 在每一行的开头插入一个0
    a.append(path)

# 初始化二维列表b，计算每个元素的差分值
b = [[0] * (m + 2) for _ in range(n + 2)]
for i in range(1, n + 1):
    for j in range(1, m + 1):
        b[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1]

# 根据输入的操作更新二维列表b的值
for _ in range(c):
    x1, y1, x2, y2, c = map(int, input().split())
    b[x1][y1] += c
    b[x2 + 1][y1] -= c
    b[x1][y2 + 1] -= c
    b[x2 + 1][y2 + 1] += c

# 初始化二维列表res，计算前缀和
# 这里我定义了一个新数组，便于大家理解，节省空间的话也可以在原数组上进行
res = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, m + 1):
        res[i][j] = res[i - 1][j] + res[i][j - 1] - res[i - 1][j - 1] + b[i][j]

# 输出最终结果
for i in range(1, n + 1):
    print(" ".join(map(str, res[i][1:])))