差分与前缀和

• 排列序数 - 蓝桥云课 (lanqiao.cn)
• 付账问题 - 蓝桥云课 (lanqiao.cn)
• 杨辉三角形 - 蓝桥云课 (lanqiao.cn)
• 寒假作业 - 蓝桥云课 (lanqiao.cn)
• 跳蚱蜢 - 蓝桥云课 (lanqiao.cn)
• 七段码 - 蓝桥云课 (lanqiao.cn)

差分法

差分法的特点：

1. 将对于区间的加减操作转化为对于端点的操作；

2. 时间复杂度为O(n):

3. 用于维护区间的增减但不能维护乘除：

4. 差分后的序列比原来的数组序列多一个数。

定义：

对于已知有n个元素得离线数列d，我们可以建立记录它与每项与前一项得差值得差分数组f；显然，f[1] = d[1] - 0 = d[1]; 对于整数 i∈[2,n]，我们让f[i]=d[i]-d[i-1]。将对d的一些操作转移至f数列，最终合并f得到d的一种操作，叫做差分法。

差分法原理解释：

例题：

首先假设有一个数组：

1 2 3 4 5 7 2

•从第二个元素到第五个元素每个+3

•从第二个元素到第四个元素每个-2

•从第一个元素到第三个元素每个+1

利用差分法解决：

#include<bits/stdc++.h>
using namespace std;
// 差分法 
const int N = 1e5+10;
//int a[N];
int a[] = {0, 1, 2, 3, 4, 5, 7, 2};
int f[N];
long long sum1 = 0, sum2 = 0;
int n = 7, m;// n = 7


int main() {
	cin>>m;
//	a[0] = 0;
	for(int i=1;i<=n;++i){
//		cin>>a[i];
		f[i] = a[i] - a[i-1];
		sum1 += a[i]; 
	}
	while(m--){
		int l, r, val;// l, r 指的是下标 
		cin>>l>>r>>val;
		l++;
		r++;
		f[l] += val;// 差分 
		f[r+1] -= val;// 差分 
	}
	for(int i=1;i<=n;++i){
		a[i] = f[i] + a[i-1];
		sum2 += a[i];// 求数组中所有元素的和 
	}
	cout<<"数组元素和(处理前)："<<sum1<<endl;
	cout<<"数组元素和(处理后)："<<sum2;
	return 0;
}

结果图：

参考：(108条消息) 差分法~超详细（公式+原理+例题）_Blind-Stab的博客-CSDN博客

前缀和

前缀和的特点：

1. 将对于区间的求和操作转化为对于端点值的减法的操作；

2. 区间求和操作的时间复杂度为0(1)；

3. 数组存放时要从1开始；

4. 前缀和数组比原来的数组序列多一个数，第0个。

前缀和算法解题的基本思路：

1. 利用sum[i]=a[i]+sum[i-1]差分式；

2. 从第1项到n项，且第0项无数据默认为0；

3. 对于区间求和的操作转化为端点值相减。

差分与前缀和恰好是一对互逆的操作

例题：

解法代码：

#include<bits/stdc++.h>
using namespace std;
// 前缀和的应用——树木维护开销 
const int N = 1e3+10;
int sum[N], a[N];
int n, m;
int L, R;

int main() {
	cin>>n>>m;
	for(int i=1;i<=n;++i){// 计算前缀和 
		cin>>a[i];
		sum[i] = sum[i-1] + a[i];// sum[0]=0 
	}
	for(int i=1;i<=m;++i){
		cin>>L>>R;
		cout<<(sum[R]-sum[L-1])<<endl;
	}
	return 0;
}