一维前缀和/差分，二维前缀和/差分

纯纯笔记，不详细不详细

代码不是题解不全是题解（是题解的能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;
}