文章目录
一、前缀和
A、一维前缀和
1、什么是一维前缀和
2、一维前缀和的作用
3、习题：Acwing 795. 前缀和
输入格式
输出格式
数据范围
输入样例：
输出样例：
4、代码详解
B、二维前缀和(矩阵和)
1、二维前缀和推导
2、习题：Acwing 796. 子矩阵的和
输入格式
输出格式
数据范围
输入样例：
输出样例：
3、代码详解
二、差分
A、一维差分
1、什么是差分
2、如何构建差分数组
3、差分数组有什么作用
4、练习 Acwing 797. 差分
输入格式
输出格式
数据范围
输入样例：
输出样例：
5、代码详解
B、二维差分(差分矩阵)
3、习题：Acwing 798. 差分矩阵
输入格式
输出格式
数据范围
输入样例：
输出样例：
4、代码详解
一、前缀和
A、一维前缀和
1、什么是一维前缀和
原数组: a[1], a[2], a[3], a[4], a[5], …, a[n]
前缀和 S[i]为数组的前 i项和
前缀和: S[i] = a[1] + a[2] + a[3] + … + a[i]
注意：前缀和的下标一定要从 1开始, 避免进行下标的转换，即定义S[0]等于0
2、一维前缀和的作用
快速求出元素组中某段区间的和
例如要求出l-r区间的和，则只需要执行sum[r]-sum[l-1]
原理如下：
sum[r] = a[1] + a[2] + a[3] + a[l-1] + a[l] + a[l+1] ...... a[r]; sum[l - 1] = a[1] + a[2] + a[3] + a[l - 1]; sum[r] - sum[l - 1] = a[l] + a[l + 1]+......+ a[r];
并且时间复杂度为O(1)
3、习题：Acwing 795. 前缀和
输入一个长度为 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
4、代码详解
#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N],sum[N]; //原数组与求和数组
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
sum[i]=sum[i-1]+a[i]; //构建前缀和
}
while(m--)
{
int L,R;
cin>>L>>R;
cout<<sum[R]-sum[L-1]<<endl;
}
return 0;
}
B、二维前缀和(矩阵和)
1、二维前缀和推导
接下来回归问题去求以(x1,y1)为左上角和以(x2,y2)为右下角的矩阵的元素的和。
如图
不难看出绿色的面积=s[x2][y2]+s[x2][y1-1]+s[x1-1][y2]-s[x1-1][y1-1]
且时间复杂度也为O(1)
2、习题：Acwing 796. 子矩阵的和
输入一个 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
3、代码详解
#include<iostream>
using namespace std;
const int N=1010;
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++){
scanf("%d",&a[i][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("%d%d%d%d",&x1,&y1,&x2,&y2);
//求并输出矩形前缀和
cout<<s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]<<endl;
}
return 0;
}
————————————————
二、差分
A、一维差分
1、什么是差分
类似于数学中的求导和积分，差分可以看成前缀和的逆运算。
这里举一个例子：
先给一个原数组a：a[1]、a[2]、a[3]、a[4]、a[5]...a[n]
然后这里再构建一个数组b:b[1]、b[2]、b[3]...b[n]
使得:a[i]=b[1]+b[2]+b[3]...b[i]
即a是b的前缀和，反过来b就是a的差分
2、如何构建差分数组
这里我们采取最暴力的做法，直接构造，并且需要注意下标，所以我们这里还是令
a[0]=0注意：下面的构造中，a为前缀和数组，b为差分数组
a[0]=0;
b[1]=a[1]-a[0];
b[2]=a[2]-a[1];
......
b[i]=a[i]-a[i-1];
3、差分数组有什么作用
我们先来看一个问题
给定区间[l ,r ]，让我们把a数组中的[ l, r]区间中的每一个数都加上c,即 a[l] + c , a[l+1] + c , a[l+2] + c ,,,,,, a[r] + c;
暴力做法是for循环l到r区间，时间复杂度O(n)，如果我们需要对原数组执行m次这样的操作，时间复杂度就会变成O(n * m)。 这个时候就体现出差分的作用了，让我们往下接着看
我们知道a是b的前缀和数组，所以改变b的一项就会改变a中有b的所有项
但是在有边界之外的也多加上一个C，如图所示
所以这里我们需要执行两步操作
b[l]+=c;
b[r+1]-=c;因此我们得出一维差分结论：给a数组中的[ l, r]区间中的每一个数都加上c,只需对差分数组b做 b[l] + = c, b[r+1] - = c。时间复杂度为O(1), 大大提高了效率。
4、练习 Acwing 797. 差分
输入一个长度为 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
输入样例：
6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1
输出样例：
3 4 5 3 4 2
5、代码详解
注意使用
scanf进行输入，效率比较高#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
b[i] = a[i] - a[i - 1]; //构建差分数组
}
int l, r, c;
while (m--)
{
scanf("%d%d%d", &l, &r, &c);
b[l] += c; //将序列中[l, r]之间的每个数都加上c
b[r + 1] -= c;
}
for (int i = 1; i <= n; i++)
{
a[i] = b[i] + a[i - 1]; //前缀和运算
printf("%d ", a[i]);
}
return 0;
}
B、二维差分(差分矩阵)
类似于前面的二维前缀和，这里引用大佬林小鹿的图解
3、习题：Acwing 798. 差分矩阵
输入一个 n行 m列的整数矩阵，再输入 q 个操作，每个操作包含五个整数 x1,y1,x2,y2,c，其中 (x1,y1)和 (x2,y2) 表示一个子矩阵的左上角坐标和右下角坐标。每个操作都要将选中的子矩阵中的每个元素的值加上 c。请你将进行完所有操作后的矩阵输出。
输入格式
第一行包含整数 n,m,q。
接下来 n行，每行包含 m个整数，表示整数矩阵。
接下来 q行，每行包含 55 个整数 x1,y1,x2,y2,c，表示一个操作。
输出格式
共 n行，每行 m个整数，表示所有操作进行完毕后的最终矩阵。
数据范围
1≤n,m≤1000
1≤q≤100000,
1≤x1≤x2≤n
1≤y1≤y2≤m
−1000≤c≤1000
−1000≤矩阵内元素的值≤1000
输入样例：
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
————————————————
4、代码详解
#include<iostream>
using namespace std;
const int N=1010;
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++)
scanf("%d",&s[i][j]);
//构建差分矩阵
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
a[i][j]=s[i][j]-s[i][j-1]-s[i-1][j]+s[i-1][j-1];
while(q--)
{
int x1,y1,x2,y2,c;
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);
a[x1][y1]+=c;
a[x1][y2+1]-=c;
a[x2+1][y1]-=c;
a[x2+1][y2+1]+=c;
}
//求和
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= m; j ++ )
printf("%d ", s[i][j]);
cout << endl;
}
return 0;
}
版权声明：本文为CSDN博主「热爱编程的小K」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_72157449/article/details/130029246
