用来降低时间复杂度的妙妙道具~
O(n)直接变成O(1)啦~~~
前缀和
一维前缀和
顾名思义，前缀和就是前缀的和。好吧我好像说了一句废话
本质上就是酱紫：
原来： a[1] , a[2] , a[3] , … a[n];
前缀和 s[i] = a[1] + a[2] + … + a[i], s[0] = 0
于是乎，只要数学合格，就可以注意力惊人地发现：
s[r] – s[l – 1] 竟然等于 a[l] + a[l + 1] + … + a[r]!
然后O(n)的时间复杂度就被我们成功地压成了O(1)
废话不多说直接贴代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m; cin >> n >> m;
vector<int> a(n + 1), s(n + 1);
for (int i = 1; i <= n; i ++ )
{
cin >> a[i];
s[i] = a[i] + s[i - 1];
}
while (m --)
{
int l, r;
cin >> l >> r;
cout << s[r] - s[l - 1] << '\n';
}
return 0;
}二维前缀和
二维前缀和就有点困难了，有点像我们小学时候学的容斥原理。
核心公式就只有两个
- 前缀和更新公式 s[i][j] = s[i – 1][j] + s[i][j – 1] +a[i][j] – s[i – 1][j – 1]
- 从(x1,y1)到(x2,y2)的矩形内的所有数的和：
sum = s[x2][y2] – s[x2][y1 – 1] – s[x1 – 1][y2] + s[x1 – 1][y1 – 1]
看着有点难记呢，但是只要画画图，再回想一下容斥原理，还是很容易推导的
最后，当然少不了贴代码环节~
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m, q; cin >> n >> m >> q;
vector a(n + 1, vector<int> (m + 1));
vector s(n + 1, vector<int> (m + 1));
for (int i = 1; i <= n ; i ++ )
{
for (int j = 1; j <= m; j ++ )
{
cin >> 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;
cin >> x1 >> y1 >> x2 >> y2;
cout << s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] << '\n';
}
return 0;
}差分
差分就是前缀和的逆运算，类比积分和导数的关系（话说你为什么不类比加法和减法啊喂）
注意，差分数组必须开大一圈，否则会访问越界。
虽然差分相当于前缀和的逆运算，但实际上这个逆运算并没有构造的必要。具体原因后续会详细说明。有具体的例子更便于理解
作用：
给定区间 [l, r] 使得a在区间中的所有的数都加上c
如果暴力做要O(n)，但是差分做只要O(1)
一维差分
首先，我们考虑有一个数组
a[1], a[2], … , a[n]
我们构造b数组，使得a[i] = b[1] + b[2] + … + b[i]，则称b为a的差分，a为b的前缀和
好的，我们现在下好定义了，然后我们只要考虑如何修改b中的元素，使得a数组的值能相应地改变
其实通过差分数组只要修改两个数即可
- b[l] + c ==> a[l] ~ a[n] 中的每一个数都加上了c
- b[r + 1] – c ==> a[r + 1] ~ a[n] 中的每一个数都减去了c
a[r + 1] ~ a[n] 中的每个数既加上了c，又减去了c，相当于没有改变。
于是我们就仅仅修改了两个数，就让a[r + 1] ~ a[n] 中的每个数都加上了c
成功降低了时间复杂度
最后不要忘记用前缀和加回来
直接贴代码
#include <bits/stdc++.h>
using namespace std;
void insert(int l, int r, int c, vector<int> &b)
{
b[l] += c;
b[r + 1] -= c;
}
int main()
{
int n, m; cin >> n >> m;
vector<int> a(n + 1), b(n + 2);
for (int i = 1; i <= n; i ++ )
{
cin >> a[i];
insert(i, i, a[i], b);
}
while (m -- )
{
int l, r, c;
cin >> l >> r >> c;
insert(l, r, c, b);
}
for (int i = 1; i <= n; i ++ )
{
b[i] += b[i - 1];
cout << b[i] << ' ';
}
cout << '\n';
return 0;
}二维差分（差分矩阵）
二维差分与一维差分相似
给子矩阵 (x1, y1) 到 (x2, y2) 加上 c 的操作如下
- b[x1][y1] + c ==> (x1, y1) 右下角所有的点都加上c
- b[x2 + 1][y1] – c ==> 一个长方形减去c
- b[x1][y2 + 1] – c ==> 一个长方形减去c
- b[x2 + 1][y2 + 1] + c ==> 正方形补上被多减去的c
与二维前缀和类似，只要结合容斥原理依然便于记忆
同样，不要忘记前缀和加回来，以及数组开到 n + 2, m + 2
#include <bits/stdc++.h>
using namespace std;
void insert(int x1, int y1, int x2, int y2, int c, vector<vector<int>> &b)
{
b[x1][y1] += c;
b[x2 + 1][y1] -= c;
b[x1][y2 + 1] -= c;
b[x2 + 1][y2 + 1] += c;
}
int main()
{
int n, m, q; cin >> n >> m >> q;
vector a(n + 2, vector<int> (m + 2));
for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= m; j ++ )
{
int tmp; cin >> tmp;
insert(i, j, i, j, tmp, a);
}
}
while(q -- )
{
int x1, y1, x2, y2, c;
cin >> 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 ++)
{
a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
cout << a[i][j] << ' ';
}
cout << '\n';
}
return 0;
}写在最后
本来以为差分会是很难理解的东西，实际上手以后发现其实并不困难，只要结合容斥原理非常便于记忆。还有，踩过的坑不要再踩，喜欢开vector的我一定要把数组开大，开大！
评论（0）
暂无评论