一、前缀和
前缀和与差分的核心思想是 预处理 ， 可以再暴力枚举的过程中 ， 快速给出查询结果 ， 从而优化时间复杂度。
是经典的用空间替换时间的做法 。
二、 一维前缀和
登录—专业IT笔试面试备考平台_牛客网
注意： 使用前缀和数组时候 ， 下标必须从 1 开始计数 ， 这样真的超级方便、简洁，规避了很多越界的情况 ， 如果你下标从0开始 ， 需要使用if 判断 ~
在来简述以下方法：
1.创建前缀和数组： f[i] = f[i − 1] + a[i]
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],f[N];//f[N]前缀和数组
int n,q; int main()
{cin >> n >> q;for(int i = 1;i<=n;i++)cin >> a[i];//处理前缀和数组for(int i = 1 ;i<=n;i++){f[i] = f[i-1] + a[i];} //处理q次询问while(q--){int l,r;cin >> l >> r;cout << f[r] - f[l-1] << endl;} return 0;
}
三、最大字段和
P1115 最大子段和 - 洛谷
#include <iostream>
using namespace std;typedef long long LL;
const int N = 2e5 + 10;
int n;
LL f[N];//前缀和数组
int main()
{cin >> n;for(int i = 1;i<=n;i++){LL x;cin >> x;f[i] = f[i-1] + x;}//初始化为负的无穷大 //因为最小字段和也可能是负数 LL ret = -1e20;LL prevmin = 0;for(int i = 1;i<=n;i++){ret = max(ret,f[i]-prevmin);prevmin = min(prevmin,f[i]);}cout << ret << endl;return 0;
}四、二维前缀和
登录—专业IT笔试面试备考平台_牛客网
#include <iostream>
using namespace std;typedef long long LL;
const int N = 1010;
int n,m,q;
LL f[N][N];int main()
{cin >> n >> m >> q;for(int i = 1;i<=n;i++){for(int j = 1;j<=m;j++){LL x;cin >> x;f[i][j] = f[i-1][j] + f[i][j-1] - f[i-1][j-1] + x;}}//处理q次查询while(q--){int x1,y1,x2,y2;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;
}五、激光炸弹
P2280 [HNOI2003] 激光炸弹 - 洛谷
#include <iostream>
using namespace std;const int N = 5010;
int n,m;
int a[N][N];
int f[N][N];//前缀和矩阵 int main()
{cin >> n >> m;while(n--){int x,y,v;cin >> x >> y >> v;x++,y++;//下标从1开始计数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];}}//枚举所有边长为m的正方形int ret = 0;m = min(m,n);//如果炸弹威力大,可以把整个区域全部都摧毁 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;} 
