设计工作网站,WordPress显示更新进度插件,wordpress联系表格7,门户网站综合型门户文章目录 差分数组引言差分数组的定义二维差分数组二维差分数组代码实现 总结OJ练习 差分数组
引言 如果给你一个包含500个元素的数组#xff0c;让你把从第一个元素到第100个元素的值都加上1#xff0c;你会毫不犹豫的说枚举#xff01;那么如果给你一个包含5000万个元素的… 文章目录 差分数组引言差分数组的定义二维差分数组二维差分数组代码实现 总结OJ练习 差分数组
引言 如果给你一个包含500个元素的数组让你把从第一个元素到第100个元素的值都加上1你会毫不犹豫的说枚举那么如果给你一个包含5000万个元素的数组让你把从第一个元素到第1000万个元素的值都加上1你会怎么做? 此时你应该怎么做如果再说暴力枚举的话那么可就有点太繁重了。为了解决这类进行大区间相同操作我们有一种较好的解决方案–差分数组。
差分数组的定义
差分数组是在原数组的基础上加以魔改的。给定数组arr我们定义数组diff其中 i0 , diff[ i ] arr[ 0 ] i 1 , diff[ i ] arr[ i ] - arr[i - 1] 我们把原来数组的每个位置上的元素和前一个元素作差得到的新数组称为差分数组(difference array)差分数组本质上就是前缀和的逆运算。
但这跟我们要解决的大区间相同操作问题又有什么关系呢
我们先来分析差分数组的特点diff[ i ] arr[ i ] - arr[ i - 1 ]那么我们如果要求arr[ i ]不就是从第0个元素一直累加到第i - 1个元素吗
假如我们有如下数组arr[] {2367111215149}
我们要求把下标4–8的元素都加上1我们发现即然第i个元素是下标0到i累加的结果那么我们如果给第0个元素加上1就能满足区间0到i上的元素全都加1同样的如果我们要把区间4-8的元素都加1我们只需要把下标4及之后的加1下标9及之后的减一即可
如图 我们发现下标4到9的diff值推算出来的原arr值都完成了加1
如果我们还想实现随机读取arr值的操作可以再增添一个前缀和数组
一维差分数组代码实现
二维差分数组
我们是否可以实现一个二分差分数组从而实现对于矩阵内的元素快速修改呢
答案是当然可以。
当然这需要你对二维前缀和有所了解见前缀和详解朴素前缀和前缀和变形二维前缀和-CSDN博客
了解了二维前缀和后我们知道对于左上角[0,0]右下角[i,j]的前缀和有
注意sum[i1][j1]为左上角[0][0]到右下角[i][j]的和 s u m [ i 1 ] [ j 1 ] s u m [ i 1 ] [ j ] s u m [ i ] [ j 1 ] − s u m [ i ] [ j ] g r i d [ i ] [ j ] . sum[i1][j1]sum[i1][j]sum[i][j1]−sum[i][j]grid[i][j]. sum[i1][j1]sum[i1][j]sum[i][j1]−sum[i][j]grid[i][j]. 我们一维差分中有如下初始化 i0 , diff[ i ] arr[ 0 ] i 1 , diff[ i ] arr[ i ] - arr[i - 1] 实际上我们不需要这样初始化只需要将差分数组diff初始化0在diff上区间修改查询arr[i]就返回arr[i] presum(diff[i])即可
由于利用差分数组查询
那么对于我们二维差分来讲我们开一个差分矩阵diff[][]当我们对矩阵grid[i][j]左上角[x][y]到右下角[i][j]的元素区间加上k时结合我们的二维前缀和公式应该对diff做如下操作 d i f f [ x ] [ y ] k ; d i f f [ x ] [ j 1 ] − k ; d i f f [ i 1 ] [ y ] − k ; d i f f [ i 1 ] [ j 1 ] k ; diff[x][y]k;\\ diff[x][j 1]-k;\\ diff[i 1][y]-k;\\ diff[i 1][j 1]k; diff[x][y]k;diff[x][j1]−k;diff[i1][y]−k;diff[i1][j1]k; 对于这个公式又有什么含义呢
diff[x][y]k造成的影响是矩阵grid从左上[x][y]到右下[m-1][n-1]的元素都会加上k因为我们求grid[i][j]时需要求diff的前缀和
但是我们只希望左上角[x][y]到右下角[i][j]的元素区间加上k时所以第2、3行的含义为
令左上角[x][j1]到右下角[m-1][n-1]都减去k令左上角[x1][j]到右下角[m-1][n-1]都减去k
此时左上角[i1][j1]到右下角[m-1][n-1]状态是加了一次k减了两次k其余区间修改都达到预期所以我们第四行
令左上角[i1][j1]到右下角[m-1][n-1]都加上k就保证了区间修改只涉及左上角[x][y]到右下角[i][j]
二维差分数组代码实现
前面说了我们差分数组只需要开一个数组维护修改值查询矩阵值的时候用修改值前缀和加上原值即可所以diff初始为0
同时为了前缀和计算没有区间越界我们开diff时开(m 2) * (n 2)大小mn为原矩阵行列数目
由于题目一般涉及到对二位差分求前缀和操作的时候一般都是离线算法所以我们只给出求diff前缀和的代码
代码如下
void update(int x , int y , int i , int j , int k)
{diff[x 1][y 1]k;diff[i 2][y 1]-k;diff[x 1][j 2]-k;diff[i 2][j 2]k;
}
void presum()//处理前缀和
{for(int i 0 ; i m ; i)for(int j 0 ; j n ; j){diff[i 1][j 1] diff[i 1][j] diff[i][j 1] - diff[i][j];
}总结
通过差分数组我们可以快速实现区间相同操作只需要改变区间左端点和右端点的下一个位置即可
差分数组常用于区间修改、离线查询等情况
OJ练习
1109. 航班预订统计 2406. 将区间分为最少组数 2381. 字母移位 II 2772. 使数组中的所有元素都等于零 2528. 最大化城市的最小供电站数目 2132.用邮票贴满网格图
