一维前缀和/差分，二维前缀和/差分
纯纯笔记，不详细不详细
代码不是题解不全是题解（是题解的能ac）
一维：
前缀和：
预处理，算出从1到 i 所有数的总和
使用场景：
在查询某一区间，如：查询 arr数组中 从 下标left 到 下标 right 的 的所有数值之和
1.如果不使用前缀和，暴力循环，时间复杂度为 o(1)（遍历数组，从left遍历到right),这样有很多次重复计算。
2.如果使用前缀和，查询时时间复杂度为 o(1)，即一次查询就算出了要求区间内的数值总和，
查询时 sum[right]-sum[left-1]
#include <iostream>
using namespace std;
int sum[1000005];
int arr[1000005];//可以不创建arr数组，因为arr[i]每个位置的数字都只用了一次->用于计算sum[i]
int main()
{ int n = 0, a = 0;cin >> n;for(int i = 1; i <= n; i++){cin>>arr[i];sum[i] = sum [i-1] + arr[i];}cin >> left >> right;cout << sum[right] - sum[left-1];return 0;
}一维差分练习:
洛谷P8218
差分：
前缀和的逆运算
使用场景：
（假设仍有 arr[100005] 数组）
差分用于同时对 （arr[1000005] ）数组某一区间的数值进行操作，而不必暴力循环
例如：对arr[x]到arr[y]同时加上某一数值z
1.构建差分数组
构建arr[]的差分数组brr[]
brr[i]=arr[i]-arr[i-1]（i从1开始，arr[0]=0=brr[0]）
brr[1]~brr[i]的 前缀和 等于 arr[i]，例如：
arr[1]=brr[1](+brr[0],brr[0]=0)
arr[2]=brr[2]+brr[1] ~~~~~ = brr[2]+arr[1]
arr[3]=brr[3]+brr[2]+brr[1] ~~~~~ brr[3]+arr[2]
......
arr[i]=brr[i]+arr[i-1]
2.原理
假设要对arr数组的 [l,r] 区间内所有值同时加上z，
1>首先,对brr[l]+z
（这时如果 再使用brr[1]~brr[i]求前缀和，得新的arr[]数组
这等效于对arr[l]~arr[i]所有数值都加z
但现在不求brr的前缀和）
2>然后，对brr[r+1]-z
这等效于对arr[r+1]~arr[i]所有数值减z
（这时如果 再使用brr[1]~brr[i]求前缀和，得新的arr[]数组
这等效于对arr[l]~arr[i]所有数值都加z
现在对求brr的前缀和，得到的结果的就是对arr[l,r]区间内所有值+z的结果）
#include <iostream>
using namespace std;
int main()
{int n = 0, p = 0, i = 0, j = 0;int x = 0, y = 0, z = 0;cin >> n >> p;for (i = 1; i <= n; i++){cin >> arr[i];brr[i] = arr[i] - arr[i - 1];}cin >> x >> y >> z;brr[x] += z;brr[y + 1] -= z;for (i = 1; i <= n; i++) {arr[i] = brr[i] + arr[i - 1];}return 0;
}一维差分练习
洛谷P2367 语文成绩
二维：
二维稍微复杂一些，配图片更容易理解，但是这里大概率没有(
前缀和：
定义数组arr[][],sum[][]
arr[][]储存输入数据
sum[][]储存arr[][]前缀和
sum[i][j]的意义是左上角为arr[1][1]~右下角为arr[i][j]的矩形区间内数值的前缀和
使用场景：
多次对某一个二维区间内数值求和（仅进行一次求和操作，之后只进行查询操作)
递推sum公式：
把左上角为arr[1][1]~右下角为arr[i][j]的矩形区间分为四个小矩形区间
（便于理解，不对arr数组真的操作）
区间1>arr[1][1]~右下角为arr[i][j-1]
区间2>arr[1][1]~右下角为arr[i-1][j]
区间3>arr[1][1]~右下角为arr[i-1][j-1]
区间4>arr[i][j]~右下角为arr[i][j],其实就是arr[i][j]
最大矩形的前缀和=（区间1.左+区间2.上-区间3.左上）前缀和 + 区间4.右下角单个arr[i][j]数值
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+arr[i][j]
#include <iostream>
using namespace std;
int arr[121][121];
int sum[121][121];
int main()
{int n = 0, i = 0, j = 0, x = 0, y = 0;int max = -0x7f7f7f, t = 0;cin >> n;for (i = 1; i <= n; i++)for (j = 1; j <= n; j++){cin >> arr[i][j];sum[i][j]+= sum[i - 1][j]+ sum[i][j - 1]- sum[i - 1][j - 1]+ arr[i][j];}for (i = 1; i <= n; i++)for (j = 1; j <= n; j++)for (x = i; x <= n; x++)for (y = j; y <= n; y++){t = sum[x][y]- sum[x][j - 1]- sum[i - 1][y]+ sum[i - 1][j - 1];if (max < t)max = t;}cout << max;return 0;
}二维前缀和练习:
洛谷P1719最大加权矩阵
差分：
二维前缀和的逆运算
使用场景：
对二维区间内某一数值进行批量操作
初始化差分数组不太方便，可以假想在一个 全0的二维矩阵（设为crr[][]） 上操作，最后将变换后的crr[][]与原arr[][]做矩阵加法
二维差分数组与一维差分数组的相似之处：
(定义原数组arr[N][N]，差分数组brr[N][N]])
对二维差分数组操作时，假设对brr[i][j]+z,等同于对arr[i][j]~arr[N][N]所有数+z
使用场景，具体操作：
对某一区间（如左上角arr[i][j]~右下角arr[x][y]）内数据全部+z
1>（便于理解，不真的对arr数组进行操作）
把左上角arr[i][j]~右下角arr[N][N]大矩形区间分为四个小矩形区间
区间1>arr[i][j]~右下角为arr[x][y]
区间2>arr[i][y+1]~右下角为arr[N][N]
区间3>arr[x+1][j]~右下角为arr[N][N]
区间4>arr[x+1][y+1]~右下角为arr[N][N]
直接对全零矩阵进行操作，不考虑初始化br人， 现在brr也是全0矩阵
（可以认为brr是全零矩阵的差分数组）
brr[i][j] += z
brr[i][y+1] -= z
brr[x+1][j] -= z
brr[x+1][y+1] += z
2>对brr求前缀和，即二维数组前缀和，得到将全零矩阵进行变换后的新矩阵
3>新矩阵和原矩阵arr相加
#include<iostream>
using namespace std;
int arr[1005][1005];
int main()
{int m = 0, n = 0;int i = 0, j = 0;int x1 = 0, y1 = 0, x2 = 0, y2 = 0;cin >> n >> m;while (m--){cin >> x1 >> y1 >> x2 >> y2;arr[x1][y1]++;arr[x1][y2 + 1]--;arr[x2 + 1][y1]--;arr[x2 + 1][y2 + 1]++;}for (i = 1; i <= n; i++){for (j = 1; j <= n; j++){arr[i][j] = arr[i][j] + arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1];cout << arr[i][j] << ' ';}cout << endl;}return 0;
}
二维差分练习:
P3397 地毯