前缀和与差分算法
一.前缀和
1.一维前缀和
给定一个数组arr，前缀和数组为sum，那么sum数组就是将从a【0】相加到a【i】的总和。
例如数组arr中有元素 1,2,3,4 那么前缀和数组则为1,1+2,1+2+3,1+2+3+4 。
有了前面的一些概念铺垫，那么前缀和有什么用呢？我们来看一个例题
题目描述
给定一个长度为n的数组a1,a2,....an
接下来有q次查询, 每次查询有两个参数l, r.
对于每个询问, 请输出al+al+1+....+ar
输入描述:
第一行包含两个整数n和q.
第二行包含n个整数, 表示a1,a2,....an
接下来q行,每行包含两个整数 l和r.
1≤n,q≤1e5
−1e9≤a[i]≤1d9
1≤l≤r≤n输出描述:
输出q行,每行代表一次查询的结果.
若每输入一组数我们就在遍历数组查找一次，那么算法的时间复杂度会变高。
所以我们可以在输入数组的时候事先对数组进行预处理，通过前缀和进行相加，当输入l和r时只需用前缀和相减就能得到范围的和，这样操作不需要遍历数组，那么时间复杂度就为 o（1）。
下面放上代码
#include <iostream>
using namespace std;
typedef long long LL;
LL ret = 0;
const int N = 1e5 + 10;
LL a[N];
LL f[N];
int main()
{
int n, q; cin >> n >> q;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
f[i] = f[i - 1] + a[i];
}
while (q--)
{
int l, r; cin >> l >> r;
ret = f[r] - f[l - 1];
cout << ret << endl;
}
return 0;
}2.二维前缀和
二维前缀和与一维前缀和相似，二维前缀和建立在矩阵上。
我们来看上图，在矩阵上的前缀和和一维的有些许不一样，点（x1-1,y1-1）的前缀和为绿色的部分，点（x2,y2）前缀和为绿色红色黄色紫色部分的和。
下面我们来看一个题
题目描述
给你一个 n 行 m 列的矩阵 A ，下标从1开始。
接下来有 q 次查询，每次查询输入 4 个参数 x1 , y1 , x2 , y2
请输出以 (x1, y1) 为左上角 , (x2,y2) 为右下角的子矩阵的和，输入描述:
第一行包含三个整数n,m,q. 接下来n行，每行m个整数，代表矩阵的元素 接下来q行，每行4个整数x1, y1, x2, y2，分别代表这次查询的参数 1≤n,m≤1000 1≤q≤1e5 −1e9≤a[i][j]≤1e9 1≤x1≤x2≤n 1≤y1≤y2≤m输出描述:
输出q行，每行表示查询结果。示例1
输入
3 4 3 1 2 3 4 3 2 1 0 1 5 7 8 1 1 2 2 1 1 3 3 1 2 3 4输出
8 25 32
首先我们输入数组并对数组进行预处理算出前缀和，若我们想计算上图（x2,y2）点的前缀和，可以用绿色+黄色（x2，y1-1前缀和）+绿色+红色（x1-1,y2前缀和）-绿色（重叠部分x1-1,y1-1前缀和）+紫色。
通过上面的算法得到前缀和最后进行还原数组
原理相同，可以理解为矩阵图形的加减，我们要求的就是一块图形，通过加减来得到。
下面放上代码
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e3 + 10;
LL a[N][N];
LL f[N][N];
LL ret;
int main()
{
int n, m, q; cin >> n >> m >> q;
for (int i = 1; i <= n; i++)//列
{
for (int j = 1; j <= m; j++)//行
{
cin >> a[i][j];
f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + a[i][j];
}
}
while (q--)
{
int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
ret = f[x2][y2] - f[x2][y1 - 1] - f[x1 - 1][y2] + f[x1 - 1][y1 - 1];
cout << ret << endl;
}
return 0;
}3.总结
当我们需要求一段区间的和时，可以使用前缀和的方法，对数组进行预处理能降低查找的复杂度。
二.差分
1.一维差分
差分算法是一种处理数组区间修改问题的高效算法，通过构建差分数组来简化区间修改。例如数组arr中有1,2,3,4元素，那么差分数组可以写成1,1,1,1. 当我们要还原数组时1,1+1,1+1+1,1+1+1+1加上前项和就能还原出原数组。
下面我们来看一个例题
题目描述
对于给定的长度为 n 的数组 {a1,a2,…,an} ，我们有 m 次修改操作，每一次操作给出三个参数 l,r,k ，代表将数组中的 al,al+1,…,ar都加上 k 。
请你直接输出全部操作完成后的数组。
输入描述:
第一行输入两个整数 n,m(1≦n,m≦1e5) 代表数组中的元素数量、操作次数。
\第二行输入 n 个整数 a1,a2,…,an(−1e9≦ai≦1e9)) 代表初始数组。
此后 m 行，每行输入三个整数 l,r,k(1≦l≦r≦n; −1e9≦k≦1e9)代表一次操作。
输出描述:
在一行上输出 n 个整数，代表全部操作完成后的数组。示例1
输入
3 2 1 2 3 1 2 4 3 3 -2输出
5 6 1
我们要对l和r区间内的数组同时加上一个k，我们可以用差分的方法对数组进行预处理，当l和r区间内的数同时加上k后，l位置会比l-1位置大k，而r位置会比原来r+1位置差值少了k。因此我们只需要对l位置的差分数组加上k，r+1位置的差分数组减去k即可。
代码样例：
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
LL a[N];
LL f[N];
int main()
{
int n, m; cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
f[i] = a[i] - a[i - 1];
}
while (m--)
{
int l, r, k; cin >> l >> r >> k;
f[l] += k, f[r + 1] -= k;
}
LL ret = 0;
for (int i = 1; i <= n; i++)
{
ret += f[i];
cout << ret << " ";
}
return 0;
}2.二维差分
二维差分就是对一个特定的矩形内进行差分运算。
如上图，若我们想要紫色的部分都加上一个k，该如何操作呢？
若我们对差分数组中点（x1,y1）加上一个k，那么这个点到右下角的整个区域相当于都加上了k，但我们只希望在紫色的部分加上k，那就需要减去多余的部分。我们对点（x1,y1）差分加上k，减去（x2+1,y1）的差分，减去（x1,y2+1）的差分，最后加上重叠被减去的部分（x2+1,y2+1）的差分。
下面来看一个例题
题目描述
给你一个n行m列的矩阵，下标从1开始。
接下来有q次操作，每次操作输入5个参数x1, y1, x2, y2, k
表示把以(x1, y1)为左上角,(x2,y2)为右下角的子矩阵的每个元素都加上k，
请输出操作后的矩阵。
输入描述:
第一行包含三个整数n,m,q. 接下来n行，每行m个整数，代表矩阵的元素接下来q行，每行5个整数x1, y1, x2, y2, k，分别代表这次操作的参数
1≤n,m≤1000
1≤q≤1e5
1≤x1≤x2≤n
1≤y1≤y2≤m
−1e9≤矩阵中的元素≤1e9输出描述:
输出n行，每行m个数，每个数用空格分开，表示这个矩阵。示例1
输入
2 3 4 1 2 3 4 5 6 1 1 2 2 3 1 2 2 3 -1 1 1 1 3 4 1 1 2 1 1输出
9 8 6 8 7 5
先对数组进行差分预处理，同时对矩阵范围进行加减，最后通过前缀和还原数组即可。
代码样例：
#include <iostream>
using namespace std;
const int N = 1010;
typedef long long LL;
LL f[N][N];
LL a[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++)
{
cin >> a[i][j];
f[i][j] += a[i][j], f[i][j + 1] -= a[i][j];
f[i + 1][j] -= a[i][j], f[i + 1][j + 1] += a[i][j];
}
}
while (q--)//差分同加同减
{
LL x1, y1, x2, y2, k; cin >> x1 >> y1 >> x2 >> y2 >> k;
f[x1][y1] += k, f[x1][y2 + 1] -= k, f[x2 + 1][y1] -= k, f[x2 + 1][y2 + 1] += k;
}
LL ret = 0;
for (int i = 1; i <= n; i++)//还原数组
{
for (int j = 1; j <= m; j++)
{
f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + f[i][j];//还原数组
cout << f[i][j] << " ";
}
cout << endl;
}
return 0;
}3.总结
当我们需要对一段区间进行同时加减时，可以使用差分算法进行预处理来降低复杂度。