c++算法之差分

发布时间:2024年01月12日

目录

差分的原理和特点

差分的实现

例题 区间更新

题目

例题2 小明的彩灯

题目描述

输入描述

输出描述


差分的原理和特点

对于一个数组a[],差分数组diff[]的定义是:

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

对差分数组做前缀和可以还原为原数组:

diff[1] = a[1]

diff[2] = a[2] - a[1]

diff[3] = a[3] - a[2]

...

diff[n] = a[n] - a[n-1]

diff[1]+diff[2]+diff[3]+...+diff[i]

=a[1]+(a[2]-a[1])+(a[3]-a[2])+...+(a[i]-a[i-1])

=a[i]

利用差分数组可以实现快速的区间修改,下面是将区间[l,r]都加上x的方法:

diff[l] += x;
diff[r+1] -= x;

在修改完成后,需要做前缀和恢复为原数组,所以上面这段代码的意思是:

diff[l]+=x表示将区间[l,n]都加上x,但是[r+1,n]我们不想加x,所以再减去x即可。

但是注意:差分数组不能实现“边修改边查询(区间和)”,只能实现“多次修改完成后多次查询”。如果要实现“边修改边查询”需要使用树状数组、线段树等数据结构。

差分的实现

直接使用循环O(n)实现即可,注意这里建议使得a[0]=0,下标从0开始。

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

将区间[l,r]加上x

diff[l]+=x;
diff[r+1]-=x;

例题 区间更新

题目

#include<iostream>
using namespace std;
const int N = 1e5+5;
int a[N],d[N];

void solve(int n, int m)
{
	for (int i = 1; i <= n; ++i)cin >> a[i];
	for (int i = 1; i <= n; ++i)d[i] = a[i] - a[i - 1];

	while (m--)
	{
		int l, r, v; cin >> l >> r >> v;
		d[l] += v;
		d[r + 1] -= v;
	}
	//前缀和还原
	for (int i = 1; i <= n; ++i)a[i] = a[i - 1] + d[i];
	for (int i = 1; i <= n; ++i)cout << a[i]<<" \n"[i == n];
}

int main()
{
	int n, m;
	cin >> n >> m;
	solve(n, m);
	return 0;
}

例题2 小明的彩灯

题目描述

小明拥有 N个彩灯,第 i 个彩灯的初始亮度为 ai。 小明将进行 Q 次操作,每次操作可选择一段区间,并使区间内彩灯的亮度 +x ( 可能为负数)。 求 Q 次操作后每个彩灯的亮度(若彩灯亮度为负数则输出 0 )。

输入描述

第一行包含两个正整数 N,Q ,分别表示彩灯的数量和操作的次数。

第二行包含 N个整数,表示彩灯的初始亮度。

接下来 Q 行每行包含一个操作,格式如下:

l r x ,表示将区间 l~r 的彩灯的亮度 +x 。

输出描述

输出共 1 行,包含 N 个整数,表示每个彩灯的亮度。

#include<iostream>
using namespace std;
using ll = long long;
const int N = 1e6+5;
ll a[N],d[N];

void solve()
{
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; ++i)cin >> a[i];
	for (int i = 1; i <= n; ++i)d[i] = a[i] - a[i - 1];

	while (m--)
	{
		int l, r, v; cin >> l >> r >> v;
		d[l] += v;
		d[r + 1] -= v;
	}
	//前缀和还原
	for (int i = 1; i <= n; ++i)a[i] = a[i - 1] + d[i];
	for (int i = 1; i <= n; ++i)cout << max(0ll,a[i])<<" \n"[i == n];
}

int main()
{

	solve();
	return 0;
}

文章来源:https://blog.csdn.net/weixin_63201442/article/details/135543754
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。