一维数组前缀和
14天阅读挑战赛
s[]数组用来储存
#include<iostream> using namespace std; #define N 100 int main() { int arr1[N]; int s[N]; int n, m; scanf("%d %d", &n, &m); for (int i = 1; i <= n; ++i) scanf("%d", &arr1[i]); for (int i = 1; i <= n; ++i) s[i] = s[i - 1] + arr1[i]; while (m--) { int l, r; scanf("%d %d", &l, &r); printf("%d", s[r] - s[l - 1]); } }
l和r确定一个区间，打印这个区间内的数组和
二维数组前缀和
#include<iostream> using namespace std; const int N = 1010; int main() { int n, m, q; scanf("%d%d%d", &n, &m, &q);//确定二维数组大小 int arr1[N][N]; int s[N][N]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { scanf("%d", &arr1[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] + arr1[i][j];//某点的区域面积，确定大区域 } } while (q--) { int x1, x2, y1, y2;//某个特定的小区域（在大区域中的小区域） scanf("%d%d%d%d", &x1, &y1, &x2, &y2);//x2,y2是最右边的点 printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]); } return 0; }
s[x][y]表示的是红色区域的数字和，加了俩次的数字要减去
(x1，y1),(x2,y2)为某区域左上角和右下角坐标，求这俩个坐标围城的矩形里数字和
差分数组
思路：
首先给定一个原数组a：a[1], a[2], a[3],,,,,, a[n];
然后我们构造一个数组b ： b[1] ,b[2] , b[3],,,,,, b[i];使得 a[i] = b[1] + b[2 ]+ b[3] +,,,,,, + b[i]
也就是说，a数组是b数组的前缀和数组，反过来我们把b数组叫做a数组的差分数组。换句话说，每一个a[i]都是b数组中从头开始的一段区间和。
考虑如何构造差分b数组？
最为直接的方法
如下：
a[0 ]= 0;
b[1] = a[1] - a[0];
b[2] = a[2] - a[1];
b[3] =a [3] - a[2];
........
b[n] = a[n] - a[n-1];
问题：
给定区间[l ,r ]，让我们把a数组中的[ l, r]区间中的每一个数都加上c,即 a[l] + c , a[l+1] + c , a[l+2] + c ,,,,,, a[r] + c;
a数组是b数组的前缀和数组，比如对b数组的b[i]的修改，会影响到a数组中从a[i]及往后的每一个数。
首先让差分b数组中的 b[l] + c ,a数组变成 a[l] + c ,a[l+1] + c,,,,,, a[n] + c;
然后我们打个补丁，b[r+1] - c, a数组变成 a[r+1] - c,a[r+2] - c,,,,,,,a[n] - c;
如果这里不打补丁，会影响这个区间后面的值
所以要打补丁
#include<iostream> using namespace std; const int N=100010; int n,m; int a[N]; int b[N]; void insert(int l,int r,int c) { b[l]+=c; b[r+1]-=c; } int main() { 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直接就是差分数组 } 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的差分，一维可以利用差分给其中一段数据加一个值，二维可以是某个矩阵加一个值，如给蓝框包围起来的矩阵加一个值
用bx1y1+=c,如果给蓝框部分加上C，则黄框-蓝框剩下的部分，也会加C，我们要减掉
黑色部分为bx2+1,y1-=C
粉色部分为bx1,y2+1-=C
但右下角被减了俩次，我们加回来一次即可+x2+1,y2+1
差分数组bij满足性质：aij是bij的前缀和
const int N=1010; int n, m, q; 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() { 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]; for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) printf("%d ", b[i][j]); return 0; }
