前缀和和差分

1,对于格式化输入输出

1，取消同步流

1	`ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);`

2，不要写

1	`cout<<endl;`

写

1	`cout<<'\n';`

3，

//举例
define ll = long long;//尽量不要用define
//替换
using ll = long long;

2,一维前缀和

a，前缀和的好处是将优化了暴力的时间复杂度

b,这是prefix的公式
$$p_i=\sum_{j=1}^ia_j=p_{i-1}+a_i$$

c，然后一般是需要求区间和，所以有以下公式$$ans=p_r-p_{l-1}$$

这是比较容易理解的

d，代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10;
ll a[N], prefix[N];
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	
	for (int i = 1; i <= n; i++) {
	cin >> a[i];
	}
	
	for (int i = 1; i <= n; i++) {
	prefix[i] = prefix[i - 1] + a[i];
	}
	int q;

	cin >> q;

	while (q--) {
	int l, r;
	cin >> l >> r;
	cout <<prefix[r] - prefix[l - 1] << '\n';
	}
}

3,一维差分

a,用途:一般地，差分主要用于让一个序列某一特定范围内的所有值都加上或减去一个常数。

b,差分：可以简单的看成序列中每个元素与其前一个元素的差。

c:差分的公式:$$d_i=a_i-a_{i-1}$$

解释为什么是这样$$\sum_{j=1}^id_j= d_1+d_2+d_3+…=(a_1-a_0)+(a_2-a_1)+…=a_i$$

d,解释为什么用差分来修改数字$$a_1=d_1 a_2=d_1+d_2 a_3=d_1+d_2+d_3$$

如果d2加1那么后面的每一项都是加1的，所以对a2后面的每一个a都是加了1的。

e,如何对a的一个区间进行修改$$在[l,r]的区间增加x\所以在l处d_l=d_l+x,\在r+1处d_{r+1}=d_{r+1}-x$$

f,重新回到a上，此时相当于a是d的前缀和，即可完成数字的修改

f，代码

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 1e5 + 10;

ll diff[N], a[N], prefix[N];

int main() {

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n;

	cin >> n;

	for (int i = 1; i <= n; i++) {

	cin >> a[i];

	}

	for (int i = 1; i <= n; i++) {

	diff[i] = a[i] - a[i - 1];

	}

	int q;

	cin >> q;

	while (q--) {

	int l, r, v;

	cin >> l >> r >> v;

	diff[l] += v;

	diff[r + 1] -= v;

	}

	int m;

	cin >> m;

	for (int i = 1; i <= n; i++) a[i] = a[i - 1] + diff[i];//

	for (int i = 1; i <= n; i++) prefix[i] = prefix[i - 1] + a[i];

	while (m--) {

	int l, r;

	cin >> l >> r;

	cout << prefix[r] - prefix[l - 1] << "\n";

	}

}

4,二维前缀和

a, https://download.tooc.xlj0.com/uploads/179/Pasted%20image%2020230918095226.png 在图片中我们可以看到我们要两块绿色相加再加上一个小块，所以蓝色部分是加多了一次所以我们要将那个部分删掉，所以我们就可以看到以下公式$$prefix_{ij}=p[i][j-1]+p[i-1][j]-p[i-1][j-1]+a[i][j]$$

b，求区间和：如果求的是区间和那么就是如图片所示 https://download.tooc.xlj0.com/uploads/179/%E7%AE%97%E6%B3%95/%E4%BA%8C%E7%BB%B4%E5%89%8D%E7%BC%80%E5%92%8C.png

可以看到有三部分，红色的点是被删了两次，所以需要加回去,所以公式如下$$求x1,y1,x2,y2这个区域的和\ans=prefix[x2][y2]-prefix[x2][y1-1]-prefix[x1-1][y2]+prefix[x1-1][x1-1]$$

d,代码实现

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 1e3 + 10;

ll prefix[N][N], a[N][N];

int main() {

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n, m, q;

	cin >> n >> m >> q;

	for (int i = 1; i <= n; i++) {

		for (int j = 1; j <= m; j++) {

			cin >> a[i][j];
	
		}

	}

	for (int i = 1; i <= n; i++) {

		for (int j = 1; j <= m; j++) {

			prefix[i][j] =

				prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + a[i][j];

		}

	}

	while (q--) {

		int x1, y1, x2, y2;

		cin >> x1 >> y1 >> x2 >> y2;

		cout << prefix[x2][y2] - prefix[x1 - 1][y2] - prefix[x2][y1 - 1] +

		prefix[x1 - 1][y1 - 1]

		<< '\n';
	
	}

}

5，二维差分

a, https://download.tooc.xlj0.com/uploads/179/%E7%AE%97%E6%B3%95/%E5%B1%8F%E5%B9%95%E6%88%AA%E5%9B%BE%202023-09-18%20110945.png 可以看到差分的操作就是将减多的部分不回来，其他部分减一份就可以$$(x1,y1)、(x2,y2)分别表示一个子矩阵的左上角和右下角的坐标，\每个操作将对应的子矩阵的每个元素加上c。$$diff[x1][y1]+=c\diff[x2+1][x1]-=c\diff[x1][y2+1]-=c\diff[x2+1][y2+1]+=c$$

b,先将a数组做差分得到一个差分的数组，对于求差分数组我们可以将左上角和右上角的坐标都看成i和j那么就是将上面的公式的x1,x2,y1,y2换成i和j。

c，然后处理后在返回去就行，接着就是前缀和的处理

d，代码

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 1e3 + 10;

ll a[N][N], d[N][N], p[N][N];

int main() {

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n, m, q;

	cin >> n >> m >> q;

	for (int i = 1; i <= n; i++) {

		for (int j = 1; j <= m; j++) {

			cin >> a[i][j];

		}

	}

	for (int i = 1; i <= n; i++) {
	
		for (int j = 1; j <= m; j++) {

			d[i][j] += a[i][j];

			d[i + 1][j] -= a[i][j];

			d[i][j + 1] -= a[i][j];

			d[i + 1][j + 1] += a[i][j];

		}

	}

	while (q--) {

	int x1, y1, x2, y2, v;

	cin >> x1 >> y1 >> x2 >> y2 >> v;

	d[x1][y1] += v;

	d[x2 + 1][y1] -= v;

	d[x1][y2 + 1] -= v;

	d[x2 + 1][y2 + 1] += v;

	}

	for (int i = 1; i <= n; i++) {

		for (int j = 1; j <= m; j++) {

			a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + d[i][j];

			cout << a[i][j] << ' ';

		}

		cout << '\n';

	}

}

6，前缀和例题鼠鼠我鸭

在一个叫做酱西功爷枝叶鸡树学院的地方有n只小动物，要么是鼠鼠，要么是鸭鸭，从1到n编号，每只小动物有个体重ai。

在这个学校里，存在一种神奇的魔法，可以将编号位于某个区间[l,r]内的所有鼠鼠都变为鸭鸭，鸭鸭都变为鼠鼠（魔法并不会改变体重）。

现在你可以施放这个魔法至多1次。（也可以不施放）

问最终鸭鸭的总重量最多是多少？

//输入格式

第一行一个整数T表示样例个数。(1≤T≤10)

对于每个样例：

第一行一个整数n表示小动物的个数。(1≤n≤1e5)

第二行n个整数，表示第i个小动物的类型。0表示鼠鼠，1表示鸭鸭。

第三行n个整数，表示第i个小动物的体重ai。(1≤ai≤1e9)
### 样例输入1
2
3
0 0 0
1 2 3
4
0 1 0 0
2 5 6 5
### 样例输出1
6
16

a，由于我们要用的是前缀和，所以思路是前缀和方面的，首先我们可以先把全部里面的鸭对应的加上，然后我们对应的是一个区间的话，那么我们可以用前缀和区间求和的方式，$prefix[r]-prefix[l-1]$所以我们现在要让这个尽量大，那我们就应该后面的尽量小，同时让prefix尽量大，所以代码如下

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 1e5 + 10;

ll a[N], prefix[N], v[N];

int main() {

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int t;
	
	cin >> t;

	while (t--) {

		int n;

		cin >> n;

		for (int i = 1; i <= n; i++) { //存贮小鸭和鼠

			cin >> a[i];

		}

		for (int i = 1; i <= n; i++) {

			cin >> v[i];

		}

		ll ans = 0;

		for (int i = 1; i <= n; i++) ans += v[i] * a[i];//把鸭全部加上

		ll mi = 0, fix = 0;//fix代标校准

		for (int i = 1; i <= n; i++) {

			if (a[i] == 0)//说明是鼠可以用魔法变成鸭

			prefix[i] = prefix[i - 1] + v[i];

			else

			prefix[i] = prefix[i - 1] - v[i];

			fix = max(fix, prefix[i] - mi);//prefix[r]-prefix[l-1]

			mi = min(mi, prefix[i]);//找到最小的prefix[l-1];

		}

		cout << ans + fix << '\n';//将偏差值加起来就行

	}

}

#基础算法

前缀和和差分

https://ljw030710.github.io/2023/09/18/前缀和和差分/

Author

iolzyy

Posted on

September 18, 2023

Licensed under

位运算(最好提前看一下逻辑运算符) Previous

day2:component组件模块化思维，Vue-Router切换页面路由 Next

前缀和和差分

1,对于格式化输入输出

2,一维前缀和

a，前缀和的好处是将优化了暴力的时间复杂度

b,这是prefix的公式$$p_i=\sum_{j=1}^ia_j=p_{i-1}+a_i$$

c，然后一般是需要求区间和，所以有以下公式$$ans=p_r-p_{l-1}$$

这是比较容易理解的

d，代码

3,一维差分

a,用途:一般地，差分主要用于让一个序列某一特定范围内的所有值都加上或减去一个常数。

b,差分：可以简单的看成序列中每个元素与其前一个元素的差。

c:差分的公式:$$d_i=a_i-a_{i-1}$$

解释为什么是这样$$\sum_{j=1}^id_j= d_1+d_2+d_3+…=(a_1-a_0)+(a_2-a_1)+…=a_i$$

d,解释为什么用差分来修改数字$$a_1=d_1 a_2=d_1+d_2 a_3=d_1+d_2+d_3$$

如果d2加1那么后面的每一项都是加1的，所以对a2后面的每一个a都是加了1的。

e,如何对a的一个区间进行修改$$在[l,r]的区间增加x\所以在l处d_l=d_l+x,\在r+1处d_{r+1}=d_{r+1}-x$$

f,重新回到a上，此时相当于a是d的前缀和，即可完成数字的修改

f，代码

4,二维前缀和

b，求区间和：如果求的是区间和那么就是如图片所示 https://download.tooc.xlj0.com/uploads/179/%E7%AE%97%E6%B3%95/%E4%BA%8C%E7%BB%B4%E5%89%8D%E7%BC%80%E5%92%8C.png

可以看到有三部分，红色的点是被删了两次，所以需要加回去,所以公式如下$$求x1,y1,x2,y2这个区域的和\ans=prefix[x2][y2]-prefix[x2][y1-1]-prefix[x1-1][y2]+prefix[x1-1][x1-1]$$

d,代码实现

5，二维差分

b,先将a数组做差分得到一个差分的数组，对于求差分数组我们可以将左上角和右上角的坐标都看成i和j那么就是将上面的公式的x1,x2,y1,y2换成i和j。

c，然后处理后在返回去就行，接着就是前缀和的处理

d，代码

6，前缀和例题鼠鼠我鸭

b,这是prefix的公式
$$p_i=\sum_{j=1}^ia_j=p_{i-1}+a_i$$