咸阳哪里做网站,小米网络营销案例分析,安徽省建设厅网站 职称,wordpress设置中文失败前缀和差分目录
1. 前缀和的概念及作用
#x1f308;概念
#x1f308;用途
#x1f319;一维前缀和
#x1f319;二维前缀和
2. 差分的概念及用途
#x1f308;概念#xff1a;
#x1f308;用途
#x1f319;一维差分
#x1f319;二维差分 1. …前缀和差分目录
1. 前缀和的概念及作用
概念
用途
一维前缀和
二维前缀和
2. 差分的概念及用途
概念
用途
一维差分
二维差分 1. 前缀和的概念及作用
概念 前缀和 对于一个给定的数列a他的前缀和数中 s 中 s[ i ] 表示从第一个元素到第 i 个元素的总和。即s[ i ] s[ i - 1 ] a[ i ]; 比如 s[ 1 ] s[ 0 ] a[ 1 ]。 注意在使用前缀和和差分的时候一般下标 0 不参与的运算统一的将下表设置为从1开始具体是要考虑到我们的边界问题也就是S[1]的求法问题为了保证我们循环的统一性我们要将S[0]设置为0所以我们索性就将下标从1开始设置起这样也有利于我们后面的初始化。 用途
可以用于一维前缀和和二维前缀和。
模板如下
一维前缀和
核心代码如下
s[i] s[i-1] a[i]
s[i] a[1] a[2] ... a[i]
a[l] ... a[r] s[r] - s[l - 1]
例题如下: 题目练习 AcWing 795. 前缀和 思路 首先做一个预处理定义一个s数组让s[ i ]代表 a 数组前 i 个数的和。 然后运用求一维前缀和运算的公式 s[i] s[i-1] a[i] 。 再进行查询操作即s[ r ] - s[ l - 1] 这样使得求 [ l, r ]的和的时间复杂度变为 O (1). 注意求 [ l, r ]的和是s[ r ] - s[ l - 1]之所以要 l - 1是因为a[ l ] 也包括在内 因为a[l] ... a[r] s[r] - s[l - 1] AC代码如下
#include iostream
using namespace std;const int N 1e510;
int a[N], s[N];int main(){int n, m, x;cinnm;for(int i 1; i n; i) cina[i];for(int i 1; i n; i) s[i] a[i] s[i - 1];int l, r;while(m--){cinlr;couts[r] - s[l - 1]endl;}return 0;
} 二维前缀和
和一维前缀和的原理类似只不过二维前缀和求的是一个矩阵中所有元素的和。
如下图 因此通过上面的图我们就可以更好理解下图来推导公式了 s[ i ][ j ] 即为框内所有数的和s[ i ][ j ]s[ i ][ j - 1 ]s[ i - 1 ][ j ] - s[ i - 1 ][ j - 1 ]a[ i ][ j ]; 而(x1, y1) 到 x2, y2的矩阵大小为s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]s[x1-1][y1-1] 核心代码
s[x][y]s[x][y-1]s[x-1][y]-s[x-1][y-1]a[x][y];
s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]s[x1-1][y1-1]
例题如下 题目练习 AcWing 796. 子矩阵的和 思路 先做一个预处理定义一个s矩阵s[ i ][ j ]代表 a 矩阵前 从00到ij的矩阵和。 然后运用求一维前缀和运算的公式 s[i] s[i-1] a[i] 。 再进行查询操作即s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]s[x1-1][y1-1]。 这样使得求 (x1, y1) 到 x2, y2的矩阵大小的和的时间复杂度变为 O (1). AC代码如下
#include iostream
using namespace std;const int N 1005;
int a[N][N], s[N][N];int main(){int n, m, q;cin n m q;//第一步输入矩阵的值for (int i 1; i n; i){for (int j 1; j m; j){cin a[i][j];}}//第二步求矩阵前缀和for (int i 1; i n; i){for (int j 1; j m; j) {s[i][j] s[i - 1][j] s[i][j - 1] - s[i - 1][j - 1] a[i][j];}}//第三步查找x1,y1到x2,y2的矩阵大小while (q--){int x1, x2, y1, y2;cin x1 y1 x2 y2;printf(%d\n, s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] s[x1 - 1][y1 - 1]);}return 0;
}2. 差分的概念及用途
概念 差分 类似于数学中的求导和积分差分可以看成前缀和的逆运算 对于一个给定的数列a其中a[1],a[2]…a[n]作为前缀和。它的差分数组中 b 中 b[ i ] 表示从第 i - 1个元素到第 i 个元素的差值。即b[ i ] a[ i ] - s[ i - 1 ]; 一维差分数组的构造也很简单即a[1] b[1], b[2] a[2] - a[1], b[n] a[n] - a[n-1] 注意刚开始时可以初始化数组a,b全部为0输入a数组后在构造时只需要将b[1]看做在[1, 1]区间上加上a[1]; b[2] 看作在[2, 2]区间上加上a[2] 用途
一维差分 差分数组的好处是可以简化运算例如想要给一个区间 [l,r] 上的数组加一个常数c原始的方法是依次加上c这样的时间复杂度是O(n)的。但是如果采用差分数组的话可以大大降低时间复杂度到O(1)。 因此只需要将b[l] b[l] c 即可这样l之后的数字会依次加上常数c而在 b[r]处将b[r1] b[r1] - c 这样r之后的数组又会恢复原值仅需要处理这两个边界的差分数组即可。时间复杂度大大降低。
核心代码如下
b[i]a[i]-a[i-1];
a[i] b[i] a[i - 1];
例题如下:
题目练习 AcWing 797. 差分 思路 首先做一个预处理定义一个b数组让b[ i ]代表a[ i ] - a[ i -1 ]. 因此只需要将b[l] b[l] c 即可这样l之后的数字会依次加上常数c而在 b[r]处将b[r1] b[r1] - c 这样r之后的数组又会恢复原值仅需要处理这两个边界的差分数组即可。 AC代码如下
#include iostream
using namespace std;const int N 1e5 5;
int b[N], a[N];int main()
{int n, m;cinnm;for (int i 1; i n; i){scanf(%d, a[i]);b[i]a[i]-a[i-1];}while(m--){int l,r,c;cinlrc;b[l]c;b[r1]-c;}for (int i 1; i n; i){a[i] b[i] a[i - 1];printf(%d , a[i]);}return 0;
} 二维差分
如果扩展到二维我们需要让二维数组被选中的子矩阵中的每个元素的值加上c,是否也可以达到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,][y21] - c; b[x21][y1] - c; b[x21][y21] c; 每次对b数组执行以上操作等价于 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才能使其恢复。 核心代码如下
b[i][j] a[i][j] − a[i − 1][j] − a[i][j − 1] a[i −1 ][j − 1]
b[x1][y1] c;
b[x2 1][y1] - c;
b[x1][y2 1] - c;
b[x2 1][y2 1] c;题目练习 AcWing 798. 差分矩阵 AC代码如下
#include iostream
using namespace std;const int N 1005;
int a[N][N], b[N][N];int main(){int n, m, q;cin n m q;for (int i 1; i n; i){for (int j 1; j m; j) {cin a[i][j];b[i][j] a[i][j] - a[i - 1][j] - a[i][j - 1] a[i - 1][j - 1];}}while (q--){int x1, x2, y1, y2, c;cin x1 y1 x2 y2 c;b[x1][y1] c, b[x2 1][y2 1] c;b[x1][y2 1] - c, b[x2 1][y1] - c;}for (int i 1; i n; i) {for (int j 1; j m; j) {a[i][j] a[i - 1][j] a[i][j - 1] - a[i - 1][j - 1] b[i][j];cout a[i][j] ;}cout endl;}return 0;
}
