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

一星

上一篇文章讲解了一维前缀和&一维差分，本篇进阶为二维。二维前缀和：二维前缀和跟一维前缀和求法相同，这里直接上例子。数组a=[[1,2,2,1],[3,2,2,1],[1,1,1,1]]a数组如图：则数组a的前缀和为：数组b[[1,3,5,6],[4,8,12,14],[5,10,15,18]]b数组如图：前缀和递推公式为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数组这样就不会报错，也不需要进行首行和首列的单独定义，更加方便理解和书写。二维差分：前文中讲到类似于数学中的求导和积分，差分可以看成前缀和的逆运算。像上述数组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输入样例：343122132211111112211323231341输出样例：234143412222方法一（很好理解）：因为差分可以看成前缀和的逆运算，可以从矩阵前缀和的构造中反推出差分矩阵。二维前缀和的递推公式为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如图所示：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，才能使其恢复。这样，我们构造二维差分数组让原二维数组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数组，类比一维差分，我们执行以下操作来使被选中的子矩阵中的每个元素的值加上cb[x1][y1]+=c;b[x1][y2+1]-=c;b[x2+1][y1]-=c;b[x2+1][y2+1]+=c;每次对b数组执行以上操作，等价于：a[i][j]+=c；我们画个图去理解一下这个过程：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，才能使其恢复。方法二的重点就在这，前面一堆废话我们可以先假想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)]foriinrange(n):path=list(map(int,input().split()))path=[0,*path]#在每一行的开头插入一个0a.append(path)#初始化二维列表b，计算每个元素的差分值b=[[0]*(m+2)for_inrange(n+2)]foriinrange(1,n+1):forjinrange(1,m+1):b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]#根据输入的操作更新二维列表b的值for_inrange(c):x1,y1,x2,y2,c=map(int,input().split())b[x1][y1]+=cb[x2+1][y1]-=cb[x1][y2+1]-=cb[x2+1][y2+1]+=c#初始化二维列表res，计算前缀和#这里我定义了一个新数组，便于大家理解，节省空间的话也可以在原数组上进行res=[[0]*(m+1)for_inrange(n+1)]foriinrange(1,n+1):forjinrange(1,m+1):res[i][j]=res[i-1][j]+res[i][j-1]-res[i-1][j-1]+b[i][j]#输出最终结果foriinrange(1,n+1):print("".join(map(str,res[i][1:])))12345678910111213141516171819202122232425262728293031323334总结：二维前缀和&二维差分也是竞赛经常考的题型，二维差分的重点在于差分数组的构造和区间的加减的，总结起来就两个公式b[x1][y1]+=c;b[x1][y2+1]-=c;b[x2+1][y1]-=c;b[x2+1][y2+1]+=c;a[i][j]=b[i][j]-b[i-1][j]-b[i][j-1]+b[i-1][j-1]两篇博客详细讲解了一维和二维的差分和前缀和，并给出了两种方法的模板题