📟作者主页:慢热的陕西人
🌴专栏链接:C++算法
📣欢迎各位大佬👍点赞🔥关注🚓收藏,🍉留言
主要讲解了前缀和和差分算法
Ⅳ. 前缀和 和 差分
Ⅵ .Ⅰ前缀和
① 一维前缀和:
就是构建一个新的数组
s
,用来存储另一个数组的和前i
个数组元素的和。用公式表达就是:
S [ i ] = a [ 0 ] + a [ 1 ] + . . . . a [ i ] S[i] = a[0]+a[1]+ .... a[i] S[i]=a[0]+a[1]+....a[i]
这个结果我们用一次遍历就可以得到(我们的S只从1开始算起,为了方便后面的计算)for(int i = 1; i < a.size(); ++i) { s[i] = s[i - 1] + a[i]; }
具体的应用就是我们可以快速得到数组一个区间
[l,r]
内元素的和。
s [ l , r ] = s [ r ] = s [ l − 1 ] s[l, r] = s[r] = s[l - 1] s[l,r]=s[r]=s[l−1]
对应题目:B3645 数列前缀和 2 - 洛谷
②二维前缀和:
二维数组的前缀和就是相当于把一位数组的前缀和拓展成二维数组的前缀和。
那么我们计算
s[i]
的表达式为:
s [ i ] [ j ] = s [ i ] [ j − 1 ] + s [ i − 1 ] [ j ] − s [ i − 1 ] [ j − 1 ] + a [ i ] [ j ] s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j] s[i][j]=s[i][j−1]+s[i−1][j]−s[i−1][j−1]+a[i][j]
那么我们计算一个子矩阵[[i,l],[j,r]]
的公式为
s [ [ i , l ] [ j , r ] ] = s [ l ] [ r ] − s [ i − 1 ] [ r ] − s [ l ] [ j − 1 ] + s [ i − 1 ] [ j − 1 ] s[[i,l][j,r]] = s[l][r] - s[i - 1][r] - s[l][j - 1] + s[i - 1][j - 1] s[[i,l][j,r]]=s[l][r]−s[i−1][r]−s[l][j−1]+s[i−1][j−1]
代码:#include<iostream> #include<stdlib.h> using namespace std; const int N = 1010; int a[N][N], s[N][N]; int main() { int n, m, q; int x1, x2, y1, y2; scanf("%d%d%d", &n, &m, & q); for(int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) scanf("%d", &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]; while (q--) { scanf("%d%d%d%d", &x1, &y1, &x2, &y2); printf("%d",(s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1])); } }
Ⅳ. Ⅱ 差分
① 一维差分
首先我们明确一个原则**差分是前缀和的逆运算,首先我们构建一个数组
b
和一个数组a
,那么我们将b
数组的前缀和存储在a
数组中,我们这时候称b
数组就是a
数组的差分**a
就是b
的前缀和。不难发现差分有这样一个性质:
在
a[l, r]
加上一个常数c
等价于b[l] += c
和b[r + 1] -= c
.这个性质非常的重要因为我们可以将
a
数组中的一些O(N)的操作降为b
数组中O(1)的操作;如下例题:
代码:
#include<iostream> #include<stdlib.h> using namespace std; const int N = 1000010; int a[N], b[N]; void insert(int l, int r, int c) { b[l] += c; b[r + 1] -= c; } int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); //利用性质算出差分 for (int i = 1; i <= n; i++) insert(i, i, a[i]); while (m--) { int l, r, c; scanf("%d%d%d", &l, &r, &c); insert(l, r, c); } //通过b计算经过操作后产生的a for (int i = 1; i <= n; ++i) b[i] += b[i - 1]; for (int i = 1; i <= n; ++i) printf("%d ", b[i]); return 0; }
②二维差分(差分矩阵)
差分矩阵和上面的一维差分的思路差不多,首先我们构建一个矩阵
b
和一个矩阵a
,那么我们将b
矩阵的前缀和存储在a
矩阵中,我们这时候称b
矩阵就是a
矩阵的差分a
就是b
的前缀和。性质上也是类似的,但是略有不同:
在
a[[x1, x2],[y1,y2]]
加上一个常数c
等价于:
b [ x 1 , y 1 ] + = c b [ x 2 , y 1 ] − = c b [ x 1 , y 2 ] − = c b [ x 2 , y 2 ] + = c b[x1,y1] += c \\ b[x2, y1] -= c\\ b[x1, y2] -= c\\ b[x2, y2] += c b[x1,y1]+=cb[x2,y1]−=cb[x1,y2]−=cb[x2,y2]+=c
例题:代码:
#include<iostream> #include<stdlib.h> using namespace std; const int N = 1010; int a[N][N], b[N][N]; void insert(int x1, int y1, int x2, int y2, int c) { b[x1][y1] += c; b[x2 + 1][y1] -= c; b[x1][y2 +1] -= c; b[x2 + 1][y2 +1] += c; } int main() { int n, m, q; scanf("%d%d%d", &n, &m, &q); for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) scanf("%d", &a[i][j]); //利用性质构造差分 for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) insert(i, j, i, j, a[i][j]); while (q--) { int x1, y1, x2, y2, c; scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c); insert(x1, y1, x2, y2, c); } //计算前缀和矩阵 for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1]; cout << endl; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) printf("%d ", b[i][j]); cout << endl; } return 0; }
到这本篇博客的内容就到此结束了。
如果觉得本篇博客内容对你有所帮助的话,可以点赞,收藏,顺便关注一下!
如果文章内容有错误,欢迎在评论区指正文章来源:https://www.toymoban.com/news/detail-596937.html
文章来源地址https://www.toymoban.com/news/detail-596937.html
到了这里,关于C++基础算法前缀和和差分篇的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!