c++算法之差分

目录

差分的原理和特点

差分的实现

例题 区间更新

题目

解

例题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;
}