原题链接
https://www.acwing.com/problem/content/description/800/
前缀和 && 差分
一维前缀和&&差分
前缀和
1 sum[i]=a[1]+a[2]+a[3].....a[i];
可以根据以上结果推出公式a[n] = a[n-1] + a[n]
差分
差分就是前缀和的逆运算。关系如下
如果 前缀和可以表示为f(x)=d 查分就是d=f(x)
具体看以下推理
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 a数组: a1, a2, a3, …, an b数组:b1, b2, b3, …, bn **a数组是b数组的前缀和** a1 = b1; a2 = b1 + b2; a3 = b1 + b2 + b3; **a数组是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]; … ..... b(n) = a(n) - a(n-1) ----> an = b1 + b2 + b3 + … + bn
前缀和的差分=原序列
差分的前缀和=原序列
所谓差分就是进行逆运算,让原数组成为新数组的前缀和,从而创造新数组。
所谓前缀和就是在这个数之前的数 和 这个数相加的总和,被称为前缀和。
1 2 3 核心部分 b[l] += c; b[r + 1] -= c;
二维矩阵 前缀和 && 差分
矩阵前缀和
1 2 3 4 5 6 7 核心部分 s[i][j] = s[i-1][j]+s[i][j-1]-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]
矩阵差分
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,才能使其恢复。
1 2 3 4 5 6 7 8 自个儿推 核心部分 b[i][j]+=a[i][j]; b[i+1][j]-=a[i][j]; b[i][j+1]-=a[i][j]; b[i+1][j+1]+=a[i][j];
相关题目
前缀和
输入一个长度为 n的整数序列。
接下来再输入 m
个询问,每个询问输入一对 l,r。
对于每个询问,输出原序列中从第 l
个数到第 r个数的和。
输入格式
第一行包含两个整数 n 和 m。
第二行包含 n个整数,表示整数数列。
接下来 m
行,每行包含两个整数 l 和 r,表示一个询问的区间范围
输出格式
共 m行,每行输出一个询问的结果。
数据范围
1≤l≤r≤n,
1≤n,m≤100000,
−1000≤数列中元素的值≤1000
输入样例:
5 3
2 1 3 6 4
1 2
1 3
2 4
输出样例:
3
6
10
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 #include <iostream> #include <cstdio> using namespace std; const int N = 1e5+10; int a[N]; int main() { int n,m; int l,r; scanf("%d%d",&n,&m); for(int i = 1;i <= n;i ++) scanf("%d",&a[i]); for(int i = 1; i <= n;i ++) a[i] = a[i-1] + a[i]; // //测试 // for(int i = 1;i <= n;i ++) // printf("%d ",a[i]); // puts(""); while(m--) { cin >> l >> r; printf("%d\n",a[r]-a[l-1]); } return 0; }
矩阵前缀和
输入一个 n 行 m 列的整数矩阵,再输入 q 个询问,每个询问包含四个整数 x1,y1,x2,y2,表示一个子矩阵的左上角坐标和右下角坐标。
对于每个询问输出子矩阵中所有数的和。
输入格式
第一行包含三个整数 n,m,q。
接下来 n行,每行包含 m个整数,表示整数矩阵。
接下来 q行,每行包含四个整数 x1,y1,x2,y2,表示一组询问。
输出格式
共 q行,每行输出一个询问的结果。
数据范围
1≤n,m≤1000
1≤q≤200000,
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include <iostream> #include <cstdio> using namespace std; const int N = 1010; int a[N][N],s[N][N]; 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 ++) s[i][j] = s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j]; while(q--) { int x1,x2,y1,y2; scanf("%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]); } return 0; }
差分
输入一个长度为 n的整数序列。
接下来输入 m个操作,每个操作包含三个整数 l,r,c,表示将序列中 [l,r] 之间的每个数加上 c。
请你输出进行完所有操作后的序列。
输入格式
第一行包含两个整数 n
和 m。
第二行包含 n个整数,表示整数序列。
接下来 m行,每行包含三个整数 l,r,c,表示一个操作。
输出格式
共一行,包含 n个整数,表示最终序列。
数据范围
1≤n,m≤100000
1≤l≤r≤n,
−1000≤c≤1000,
−1000≤整数序列中元素的值≤1000
输入样例:
1 2 3 4 5 6 3 1 2 2 1 2 1 1 3 1 3 5 1 1 6 1
输出样例:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include <iostream> #include <cstdio> using namespace std; const int N = 1e5+10; int a[N]; int b[N]; int main() { int n,m; scanf("%d%d",&n,&m); for(int i = 1;i <= n;i++) scanf("%d",&a[i]); //构造差分数组b1=a1,b2=a2-a1,b[n]=a[n]-a[n-1]; for(int i = 1;i <= n;i++) b[i]=a[i]-a[i-1]; //看链接 https://www.acwing.com/solution/content/26588/ while(m--) { int l,r,c; scanf("%d%d%d",&l,&r,&c); b[l]+=c; b[r+1]-=c; } //把差分数组还原成原数组 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; }
矩阵差分
输入一个 n 行 m 列的整数矩阵,再输入 q 个操作,每个操作包含五个整数 x1,y1,x2,y2,c,其中 (x1,y1) 和 (x2,y2)表示一个子矩阵的左上角坐标和右下角坐标。
每个操作都要将选中的子矩阵中的每个元素的值加上 c。
请你将进行完所有操作后的矩阵输出。
输入格式
第一行包含整数 n,m,q。
接下来 n行,每行包含 m个整数,表示整数矩阵。
接下来 q行,每行包含 5 个整数 x1,y1,x2,y2,c,表示一个操作。
输出格式
共 n行,每行 m个整数,表示所有操作进行完毕后的最终矩阵。
数据范围
1 2 3 4 5 6 1≤n,m≤1000, 1≤q≤100000, 1≤x1≤x2≤n, 1≤y1≤y2≤m, −1000≤c≤1000, −1000≤矩阵内元素的值≤1000
输入样例:
1 2 3 4 5 6 7 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
输出样例:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 #include <cstdio> #include <iostream> using namespace std; const int N = 5010; int a[N][N],b[N][N]; void insert(int x1,int y1,int x2,int y2,int c) { b[x1][y1] += c; b[x1][y2+1] -= c; b[x2+1][y1] -= 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]); //对差分数组进行+c操作 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); } //转换成a数组,由差分数组,求前缀和 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]); puts(""); } return 0; }