Acwing 前缀与差分
1.一维前缀和
一维前缀和:S[i]=a1+a2+a3+a4+…+ai,要求a从a1开始,且S[0]=0
前缀和的作用:给定一组序列数据,可以计算任意第l个数到第r个数的和,S[r]-S[l-1](这里就解释了为什么要求S[0]=0,因为当l=1时,实质就是求是S[r])
求很多个任意子序列的数据和时,假如不使用前缀和公式,就需要顺序遍历来求,时间复杂度为O(n)
使用前缀和,直接得到结果,时间复杂度为O(1)
Acwing 795.前缀和
具体实现代码(详解版):
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N],s[N];
int n,m;
int main(){
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];//计算前缀和,s[0] = 0
//处理询问
while(m --){
int l , r;
cin >> l >> r;
cout << s[r] - s[l - 1] << endl;//使用前缀和
}
return 0;
}
2.二维前缀和
二维前缀和:S[i][j]
即为坐标(i,j)
左上部分所有元素的和,也就是绿色区域的所有元素和(注意i,j依旧是从1开始,s[0][0]
默认为0)
二维前缀和计算公式:s[i][j]
=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j]
(注意这里要s[i][j-1]+s[i-1][j]
多算了一次s[i-1][j-1]
,所以要减去一次)
任意子矩阵中所有数的和计算:
设所求子矩阵的左上角坐标为(x1,y1),右下角坐标为(x2,y2)
s=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]
eg:s=S[5][3] - S[2][3] - S[5][1] + S[2][1]
具体实现代码(详解版):
#include <iostream>
using namespace std;
const int N = 1010;
int a[N][N], s[N][N]; // a 用于存储原始矩阵,s 用于存储二维前缀和
int n, m, q; // n: 行数, m: 列数, q: 查询的次数
int main() {
cin >> n >> m >> q;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
}
}
// 计算前缀和矩阵 s
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];
}
}
// 处理 q 次查询
while (q--) {
int res = 0; // 存储子矩阵的和
int x1, y1, x2, y2; // 子矩阵左上角 (x1, y1) 和右下角 (x2, y2)
cin >> x1 >> y1 >> x2 >> y2;
// 利用前缀和公式计算子矩阵的和
res = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
cout << res << endl;
}
return 0;
}
3.一维差分
差分的实质是前缀和的逆运算
假设有一个数组,a{1},a{2},a{3},a{4},a{5},…,a{n}
针对这个数组,构造出另一个数组,b{1},b{2},b{3},b{4},b{5},…,b{n}
使得a数组是b数组的前缀和,即使得 a{i} = b{1} + b{2} + … + b{i};b{i}=a{i}-a{i-1}
差分的作用:
若要对a数组中[l, r]区间内的全部元素都加上一个常数C,若直接操作a数组的话,需要循环遍历,时间复杂度是O(n)。而如果操作其差分数组b,则时间复杂度是O(1)。即可以用O(1)的时间给某一数组的某一子序列元素都加上一个值
具体实现:
数组a是数组b的前缀和数组,只要对 b{l}这个元素加C,则a数组从l位置之后的全部数都会被加上C,但r位置之后的所有数也都加了C,所以我们通过对 b{r+1} 这个数减去C,来保持a数组中r位置以后的数的值不变,即a数组r位置以后的数都是+C-C抵消。
于是,对a数组的[l, r]区间内的所有数都加上一个常数C,就可以转变为对b{l}+C
,对b{r+1}-C
。
对于构造差分数组b:
在输入数组a时,可以先假想数组a和数组b的全部元素都是0。然后每次进行一次插入操作(指的是对数组a的[l, r]区间的每个数加上常数C),比如对a数组区间[1,1],加(插入)常数a{1},效果就是b{1}=b{1}+a{1}
,b{2}=b{2}-a{1}
;对区间[2,2],加常数a{2},效果就是b{2}=b{2}+a{2}
,b{3}=b{3}-a{2}
,…,这样在输入数组a的同时,就能够快速构造出其差分数组b。实际就把构造数组b的过程看作为给一个数组中[l, r]区间内的全部元素都加上一个常数C的过程,只不过特殊的是这个数组元素都为0,这个区间为[i,i],这个常数C会变化为a[i]
具体实现代码(详解版):
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N], b[N]; // a 用于存储初始数组,b 为差分数组
int n, m; // n: 数组大小, m: 操作次数
// 插入操作,差分数组的更新
void insert(int l, int r, int c) {
b[l] += c; // 在区间左端点加上 c
b[r + 1] -= c; // 在区间右端点的下一个位置减去 c
}
int main() {
cin >> n >> m;
// 读取初始数组 a 的值,并将其转换为差分数组 b
for (int i = 1; i <= n; i++) {
cin >> a[i]; // 读入初始数组
}
for (int i = 1; i <= n; i++) {
insert(i, i, a[i]); // 将初始数组 a 构造成差分数组 b
}
// 处理 m 次操作
while (m--) {
int l, r, c;
cin >> l >> r >> c; // 读入操作:对区间 [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++) {
cout << b[i] << ' ';
}
cout << endl; // 换行
return 0;
}
4.二维差分
类比一维差分和二维前缀和,二维差分的作用:以时间复杂度O(1)对任意子矩阵加上一个常数
具体实现:
期望对矩阵a中左上角为[x1, y1],右下角为[x2, y2]的区域内的全部元素,都加一个常数C,则可以转化为对其差分矩阵b的操作。
先对b中[x1, y1]位置上的元素加C,这样以来,前缀和a中[x1, y1]这个点的右下角区域内的所有数都加上了C,但是这样就对[x2, y2]之后的区域也都加了C。 我们对[x2, y2]之外的区域需要保持值不变,所以需要进行减法。对b{x2+1,y1} 减掉C,这样下图红色区域都被减了C,再对b{x1,y2+1}减掉C,这样下图蓝色区域都被减了C,而红色区域和蓝色区域有重叠,重叠的区域被减了2次C,所以要再加回一个C,即对b{x2+1,y2+1}加上一个C。这样,就完成了对[x1,y1],[x2, y2]区域内的所有数(下图绿色区域),都加上常数C。
构造差分二维数组b
思想和一维差分一样,假设二维数组a和二维数组b初始化都为0,在输入a[i][j]
时就可顺便构造b[i][j]
。实际就把构造数组b的过程看作为给一个数组中[x1, y1],[x2, y2]区域内的全部元素都加上一个常数C的过程,只不过特殊的是这个数组元素初始都为0,这个区域为[i,j]到[i,j](即就是一个元素),这个常数C会变化为a[i][j]
具体实现代码(详解版):
#include <iostream>
using namespace std;
const int N = 1010;
int a[N][N], b[N][N]; // a 用于存储原始矩阵,b 用于存储差分矩阵
int n, m, q;
// 插入操作:更新差分矩阵 b,反映在子矩阵 (x1, y1) 到 (x2, y2) 中加上常数 c 的操作
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() {
cin >> n >> m >> q;
// 输入原始矩阵 a
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
}
}
// 构造差分矩阵 b,基于初始矩阵 a
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;
cin >> 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] + b[i][j];
}
}
// 输出更新后的最终矩阵
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cout << b[i][j] << ' ';
}
cout << endl;
}
return 0;
}
以上就是前缀和差分的基本应用,前缀和除了在这里和差分一起使用外,后续还会有应用。(主要的就说要推导并记住一维和二维前缀和的公式)
s[i] = s[i] + a[i];//计算一维前缀和
res = s[r] - s[l-1];//计算l-r的区间和
s=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];//计算二维前缀和
res = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]; 利用前缀和公式计算子矩阵的和
差分的重点是构造差分数组:
//一维
// 插入操作,差分数组的更新
void insert(int l, int r, int c) {
b[l] += c; // 在区间左端点加上 c
b[r + 1] -= c; // 在区间右端点的下一个位置减去 c
}
...
insert(i, i, a[i]); // 将初始数组 a 构造成差分数组 b
//二维
// 插入操作:更新差分矩阵 b,反映在子矩阵 (x1, y1) 到 (x2, y2) 中加上常数 c 的操作
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;
}
...
insert(i, j, i, j, a[i][j]);// 构造差分矩阵 b,基于初始矩阵 a
原文地址:https://blog.csdn.net/qq_43060884/article/details/142914751
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!