算法学习（三）前缀和差分

前缀和：Sn 类似于积分

差分：dn 类似于微分

1、一维前缀和

#include<iostream> using namespace std; /* 对于每个询问，输出原序列中从第l个数到第r个数的和 第一行包含2个整数：n和m 第二行包含n个整数，表示整块数列 接下来m行，每行都包含2个整数l和r,表示一个询问区间范围 1<= l <= r <= n 1<=n,m<=100000 -1000<= 数列中元素的值 <= 1000 */ const int N = 100010; int n, m,l,r; int a[N], s[N] = { 0 }; int main() { cin >> n >> m; for (int i = 1; i <= n; i++) scanf_s("%d", &a[i]); // 前缀和初始化 for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i]; // 区间和计算 while (m--) { scanf_s("%d %d", &l, &r); cout << s[r] - s[l - 1] << endl; } } /* 5 3 2 1 3 6 4 1 2 1 3 2 4 答案： 3 6 10 */

或

#include<iostream> using namespace std; const int N = 100010; int n, m,l,r; int a[N], s[N] = { 0 }; int main() { std::ios::sync_with_stdio(false); /* 取消cin于stdin的同步,与scanf效率相差无几;不可以与scanf混用,但是还是没有scanf的速度快 要不就全部scanf,printf, 要不就ios::sync_with_stdio(false)+全部cin,cout， 不要混用避免不必要的WA. */ cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i]; while (m--) { cin >> l >> r; cout << s[r] - s[l - 1] << endl; } } /* 5 3 2 1 3 6 4 1 2 1 3 2 4 答案： 3 6 10 */

2、二维前缀和

#include<iostream> using namespace std; /* * 范围： 1<=n,m<=1000 1<=q<=10000 1<=x1<=x2<=n 1<=y1<=y2<=m -1000<=元素的值<=1000 输入样例： 3 4 3 1 7 2 4 3 6 2 8 2 1 2 3 1 1 2 2 2 1 3 4 1 3 3 4 输出样例： 17 27 21 */ const int N = 1010; int n, m, q,i,j; int a[N][N], s[N][N]; int main() { scanf_s("%d%d%d", &n, &m, &q); for ( i = 1; i <= n; i++) for ( j = 1; j <= m; j++) scanf_s("%d", &a[i][j]); for (i = 1; i <= n; i++) for (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--) { int x1, y1, x2, y2; scanf_s("%d%d%d%d", &x1, &y1, &x2,&y2); printf("%d\n", s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]); } }

3、一维差分

#include<iostream> using namespace std; /* 输入：长度为n的整数序列 再输入 ：m个操作，每个操作包含3个整数l,r,c:表示将序列中[l,r]直接的每个数都加上c. 第一行：n,m 第二行n个整数 m行,每行:l,r,c 输出格式：1行,n个整数,表示最终序列。 1<=n,m<=10000; 1<=l<=r<=n, -1000<=c<=1000 -1000<=整数序列中元素的值<=1000 输入样本： 6 3 1 2 2 1 2 1 1 3 1 3 5 1 1 6 1 输出样例： 3 4 5 3 4 2 */ const int N = 100010; int a[N], b[N]; int n, m,i,l,r,c; // 核心算法 void insert(int l, int r, int c) { b[l] += c; b[r+1] -= c; } int main(){ scanf_s("%d%d", &n, &m); for (i = 1; i <= n; i++) scanf_s("%d", &a[i]); for (i = 1; i <= n; i++) insert(i, i, a[i]); // 得到原来b序列 while (m--) { scanf_s("%d%d%d", &l, &r, &c); insert(l, r, c); } for (i = 1; i <= n; i++) b[i] += b[i - 1]; for (i = 1; i <= n; i++) printf("%d ", b[i]); }

4、二维差分

#include<iostream> using namespace std; /* 输入：一个n*m的整数矩阵 再输入q个操作包括五个整数x1,y1,x2,y2,c； 其中(x1,y1)和(x2,y2)表示一个子矩阵的左上角坐标和右下角坐标 每个操作要把选中的子矩阵中的每个元素的值都加上c 输入格式： 第一行: n,m,q n行：每行包含m个整数，表示整数矩阵 输出格式： 共n行，每行m个整数，表示所有操作进行完毕后的最终矩阵。 数据范围： 1<=n,m<=1000 1<=q<=100000 1<=x1<=x2<=n 1<=y1<=y2<=m 输入样例： 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 */ const int N = 1010; int a[N][N], b[N][N]; int n, m, q,i,j; // 核心算法 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() { scanf_s("%d%d%d", &n, &m, &q); for (i = 1; i <= n; i++) for (j = 1; j <= m; j++) scanf_s("%d", &a[i][j]); for (i = 1; i <= n; i++) for (j = 1; j <= m; j++) insert(i, j, i, j, a[i][j]); int x1, y1, x2, y2,c; while (q--) { scanf_s("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c); insert(x1, y1, x2, y2, c); } for(i=1;i<=n;i++) for(j=1;j<=m;j++) b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] ; for (i = 1; i <= n; i++) { for (j = 1; j <= m; j++) { printf("- ", b[i][j]); } printf("\n"); } }