算法基础—前缀和
目录
1 ⼀维前缀和
2 最⼤⼦段和
3 ⼆维前缀和
4.激光炸弹
前缀和与差分的核⼼思想是预处理，可以在暴⼒枚举的过程中，快速给出查询的结果，从⽽优化时间复杂度。是经典的⽤空间替换时间的做法
1 ⼀维前缀和
题⽬来源： ⽜客⽹
题⽬链接：【模板】前缀和
难度系数： ★
【解法】
解法一：暴力解法-> 模拟（但是时间复杂度是O(nq)->10^10会超时）
解法二：前缀和->快速求出数组中，某一段的区间和（时间复杂度O(1)）
1.先预处理出来一个前缀和数组f[i] = f[i - 1] + a[i]
注意事项：使用前缀和数组时，下表要从1开始计数（可以避免很多边界问题）
2. 查询 [l, r] 区间和： f[r] - f[l - 1]
【参考代码】
#include<iostream>
using namespace std;typedef long long LL;
const int N = 1e5 + 10;
LL a[N];
LL f[N];//前缀和数组
int n,q,l,r;int main(){cin >> n >> q;for(int i = 1;i <= n;i++){cin >> a[i];}//处理前缀和数组 for(int i = 1;i <= n;i++){f[i] = a[i] + f[i-1];}//处理q次询问 while(q--){cin >> l >> r;cout << f[r]-f[l-1] << endl;}return 0;
}2 最⼤⼦段和
题⽬来源： 洛⾕
题⽬链接： P1115 最⼤⼦段和
难度系数： ★★
【解法】
关于这道题的解法有很多种，这里先介绍利⽤「前缀和」的解法。
考虑以 i 位置的元素 a[i] 「为结尾」的最⼤⼦段和：
- 在求「区间和」时，相当于是⽤ f[i] 减去 i 位置前⾯的某⼀个 f[x] ；
- 如果想要「最⼤⼦段和」，也就是「最⼤区间和」，那么⽤ f[i] 减掉⼀个「前驱最⼩值」即可。
因此，我们可以创建 数组的「前缀和」数组，然后在遍历前缀和数组的过程中，⼀边「更新前驱最⼩值」，⼀边「更新当前位置为结尾的最⼤⼦段和」
【参考代码】
#include<iostream>
using namespace std;const int N = 2e5 + 10;
typedef long long LL;
LL f[N];
int n;int main(){cin >> n;//计算前缀和 for(int i = 1;i <= n;i++){int x;cin >> x;f[i] = f[i-1] + x;}//求最大子段和 LL ret = -1e20;//最大子段和 LL prevmin = 0;//i前面的最小前缀和 for(int i = 1;i <= n;i++){ret = max(ret,f[i] - prevmin);prevmin = min(f[i],prevmin);} cout << ret << endl;return 0;
} 3 ⼆维前缀和
题⽬来源： ⽜客⽹
题⽬链接：【模板】⼆维前缀和
难度系数： ★
【解法】
解法一：暴力解法->模拟（最差时间复杂度O(qnm)->10^11,会超时）
解法二：二维前缀和->快速查询二维数组中，某一个子矩阵中所有元素的和
1.创建前缀和矩阵： f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + a[i][j]
2.查询以 (x1 , y 1) 为左上⻆ , (x2 , y 2) 为右下⻆的⼦矩阵的和
【参考代码】
#include<iostream>
using namespace std;const int N = 1010;
typedef long long LL;
LL f[N][N];
int n,m,x1,x2,y1,y2,q;int main(){cin >> n >> m >> q;for(int i = 1;i <= n;i++){for(int j = 1;j <= m;j++){int x; cin >> x;f[i][j] = f[i-1][j] +f[i][j-1] -f[i-1][j-1] + x;}}while(q--){cin >> x1 >> y1 >> x2 >> y2;cout << f[x2][y2] - f[x1-1][y2] - f[x2][y1-1] + f[x1-1][y1-1] << endl;}return 0;
}4.激光炸弹
题⽬来源： 洛⾕
题⽬链接： [HNOI2003]激光炸弹
难度系数： ★★
分析题意得：如果想尽可能多 的摧毁目标，炸弹的边应该和矩阵的边重叠。
【解法】
暴力枚举->在坐标系中枚举出所有边长为m的正方形，找出正方形中目标价值最大的即可；
如何枚举边⻓为 m 的所有正⽅形：
- 仅需枚举右下⻆[x2 , y2 ] ，那么结合边⻓ 就可算出左上⻆ 。
- 代⼊前缀和矩阵中，就可以快速求出这个正⽅形内所有⽬标的总价值
#include<iostream>
using namespace std;const int N = 5010;
int a[N][N];
int f[N][N];
int m,n;
int x,y,v;
int main(){cin >> n >> m;for(int i = 0;i < n;i++){cin >> x >> y >> v;x++;y++;a[x][y] += v;}n = 5001;//前缀和 for(int i = 1;i <= n;i++){for(int j = 1;j <= n;j++){f[i][j] = f[i-1][j] + f[i][j-1] -f[i-1][j-1] + a[i][j];}}int ret = 0;for(int x2 = m;x2 <= n;x2++){for(int y2 = m;y2 <= n;y2++){int x1 = x2 - m +1;int y1 = y2 - m + 1;ret = max(ret,f[x2][y2] - f[x1-1][y2] - f[x2][y1-1] + f[x1-1][y1-1]);}} cout << ret << endl;return 0;
}