算法学习之路：前缀和与差分详解
算法学习之路：前缀和与差分详解
前缀和与差分是算法中常用的优化技巧，广泛应用于数组和矩阵的区间查询与修改问题。本文将系统地介绍一维和二维前缀和的定义、公式及其应用，同时深入讲解差分的概念和具体实现方法。通过详细的代码示例和实战题目，帮助读者全面掌握这一重要算法技巧。
前言
在算法学习的道路上，前缀和与差分是两个非常重要的概念。它们不仅能够优化代码的执行效率，还是解决许多复杂问题的关键工具。本文将从基础概念出发，逐步深入讲解一维和二维前缀和，以及一维和二维差分的原理和应用。通过具体的代码示例和实战题目，帮助读者全面掌握这些算法技巧。
一.前缀和
1.什么是前缀和
前缀和可以简单的理解为数列的前n项和，是一种重要的预处理方式。（建议：在写前缀和与差分时数组的下标从1开始，后面未提到下标从0开始则是从1开始。)
2.一维前缀和
（1）一维前缀和的定义
一维前缀和（sum数组）的第i个元素就是从数组（a数组）的第一个元素开始加到第i个元素。
sum[i] = a[1] + a[2] + …a[i];
（2） 一维前缀和的公式
sum[i] = sum[i - 1] + a[i];
将数组sum中所有的值都初始化为零，sum[1] = sum[0] + a[1] = a[1]，这也就是为什么建议数组的下标从1开始的原因之一，不需要特殊处理第一个元素。
另外还有一条建议，在接收数据是可以将sum放到for循环中,这样的代码更加简洁：
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum[i] = sum[i - 1] + a[i];
}
其他重要知识：如果求[l,r]区间的和其公式为：
s = sum[r] - sum[l - 1];
不是s = sum[r] - sum[l];
因为：
s = a[l] + … +a[r];
sum[r] = a[1]+ … +a[l - 1] + a[l] + … + a[r];
sum[l - 1] = a[1]+ … +a[l - 1] ;
这点不注意很容易犯错，请牢牢记住！！！
（3）一维前缀和的题目
题目：洛谷B3612 【深进1.例1】求区间和
#include <iostream>
using namespace std;
int an[100005];
int sum[10005];
int n, m;
int l, r;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> an[i];
sum[i] = sum[i - 1] + an[i];
}
cin >> m;
for (int i = 0; i < m; i++) {
cin >> l >> r;
cout << sum[r] - sum[l - 1] << endl;
}
return 0;
}
（4）总结
一维前缀和比较简单，比赛一般和其他算法结合考，是用来优化代码的，求[l,r]区间的和其公式不注意很容易犯错，其他的没什么了。
3.二维前缀和
（1）二维前缀和的定义
与一维数组有点不同，二维数组的二维前缀和不是从第一个元素加到第i个元素，其二维前缀和是以a[1][1]和a[i][j]两个顶点的矩形，其矩形内所有元素加起来的和，如图：
（2） 二维前缀和的公式
二位前缀和公式的求解方法是基于容斥原理（先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。），如图：
想要求出sum[8][2]，则：
先加上sum[7][2];
在加上sum[8][1];
再减去加了两次的sum[7,1],最后再加上a[8][2],注意：只有最后一次是加上a数组的，前几次都是加减sum数组，不懂为什么的可以多看几遍二维前缀和的定义。
所有其公式为：
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
当然，同样可以边输入边求前缀和。
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> nums[i][j];
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + nums[i][j];
}
}
其他重要知识点：如果要求a[x1][y1]到a[x2][y2]的和其公式为
ans = sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1-1][y1-1];
（3）二维前缀和的题目
题目：洛谷P1387 最大正方形
#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
int nums[105][105];
int sum[105][105];
int ans;
int l = 1;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> nums[i][j];
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + nums[i][j];
}
}
int k = min(n, m);
while (l <= k) {
for (int i = l; i <= n; i++) {
for (int j = l; j <= m; j++) {
if (sum[i][j] - sum[i - l][j] - sum[i][j - l] + sum[i - l][j - l] == l * l) {
ans = max(ans, l);
}
}
}
l++;
}
cout << ans;
return 0;
}
（4）总结
二维前缀和也比较简单，遇到与矩阵相关的题目很有可能就要要用到二维前缀和。
原数组就是sum数组的差分数组。
二.差分
1.什么是差分
差分是一种和前缀和相对的策略，可以当做是求和的逆运算。
2.一维差分
（1）一维差分标记数组
通过对a数组很少的修改，但有很多改变sum数组的操作,一维差分数组可以高效的处理区间修改问题。
（2） 一维差分的公式
在给区间[l,r]范围内加上q，则公式为：
a[l] + q;
a[r + 1] - q;
若在区间[1,3]加1，则如图：
（3）一维差分的题目
洛谷P1083 NOIP2012 提高组 借教室
#include <cstdio>
#include <cstring>
using namespace std;
const long long MAX_SIZE = 1000005;
bool isOk(long long x, long long n, const long long d[], const long long start[], const long long end[], const long long capacity[], long long diff[], long long need[]) {
memset(diff, 0, sizeof(int) * MAX_SIZE);
for (int i = 1; i <= x; ++i) {
diff[start[i]] += d[i];
diff[end[i] + 1] -= d[i];
}
for (int i = 1; i <= n; ++i) {
need[i] = need[i - 1] + diff[i];
if (need[i] > capacity[i]) {
return false;
}
}
return true;
}
int main() {
long long n, m;
long long diff[MAX_SIZE], need[MAX_SIZE], capacity[MAX_SIZE], start[MAX_SIZE], end[MAX_SIZE], d[MAX_SIZE];
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%d", &capacity[i]);
}
for (int i = 1; i <= m; ++i) {
scanf("%d%d%d", &d[i], &start[i], &end[i]);
}
if (isOk(m, n, d, start, end, capacity, diff, need)) {
printf("0");
return 0;
}
long long left = 1, right = m;
while (left < right) {
long long mid = left + (right - left) / 2;
if (isOk(mid, n, d, start, end, capacity, diff, need)) {
left = mid + 1;
}
else {
right = mid;
}
}
printf("-1\n%d", left);
return 0;
}
（4）总结
通过一维差分标记数组 可以快速的修改区间的值和计算数组区间和。
3.二维差分
（1）二维差分标记数组
通过二维差分标记数组可以加减一个矩形内的值而不影响矩形外元素的值，相比于直接for循环遍历，时间上会快上不少。
（2） 二维差分的公式
二维差分标记数组相比与一维差分标记数组来说变得有点抽象了，若把a[x1][y1]到a[x2][y2]这个矩形内的元素都加上q,则：
a[x1][y1] + q,
a[x1][y2 +1] - q,
a[x2+1][y1] - q,
a[x2+1][y2+1] + q;
如图：
每个操作的颜色代表了其影响的范围，第一次操作使黄色的地方的sum值加一，第二次操作使红色的地方的sum值减一，第三次操作使绿色的地方的sum值减一，第四次操作使蓝色的地方的sum值加一，最终相互抵消使a[x1][y1]到a[x2][y2]这个矩形内的值变化而不影响矩形外元素的值。那么肯定有人不理解了，为什么他影响的范围就是这个矩形，通过二维前缀和的公式，和二维前缀和的公式的其他重要知识便可以得出结论：
ans = sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1-1][y1-1];
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
sum[i][j] = a[0][0] +… + a[i][j];
因为未加减值的点的值初始化为零
最后化简可得：
从a[x1,y1]到你所要求的点形成一个矩形，其sum值为该矩形内所有加减值的总和。
（3）二维差分的题目
题目：洛谷P3397 地毯
#include <iostream>
using namespace std;
int n, m;
int map[1005][1005];
int sum[1005][1005];
int x, y, x1, z;
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> x >> y;
map[x][y] += 1;
cin >> x1 >> z;
map[x][z + 1] -= 1;
map[x1 + 1][y] -= 1;
map[x1 + 1][z + 1] += 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + map[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << sum[i][j] << " ";
}
cout << endl;
}
return 0;
}
（4）总结
二维差分标记数组可以利用在加减一个矩形内的值而不影响矩形外元素的值
总结
前缀和与差分是算法中非常重要的优化技巧，广泛应用于数组和矩阵的区间查询与修改问题。通过本文的系统学习，读者应该能够掌握一维和二维前缀和的定义、公式及其应用，同时深入理解差分的概念和具体实现方法。这些知识对于算法竞赛和实际开发中的性能优化都具有重要意义。