一维差分
题目描述
输入一个长度为 n 的整数序列。
接下来输入 m 个操作,每个操作包含三个整数 l, r, c, 表示将序列中 [l, r] 之间的每个数加上 c 。
请你输出进行完所有操作后的序列。
输入格式
第一行包含两个整数 n 和 m。
第二行包含 n 个整数,表示整数序列。
接下来 m 行,每行包含三个整数 l,r,c,表示一个操作。
输出格式
共一行,包含 n 个整数,表示最终序列。
数学原理
现有原数组 an
若想将数组下标为 [L, R] 之间的每个数加上 c, 朴素做法需要执行 L - R + 1 次操作。
若利用差分数组只需执行 2 次操作。
原理:
规定任意数组An, A0=0; R >= L
现通过以下方法构造差分数组 bn
bi = ai - ai−1
则差分数组 bn 具有以下性质
∑n1 bi = (a1 - a0) + (a2 - a1) + … + (an - an−1) = an - a0 = an
即 an = ∑n1 bi
构造新数组 b∗n
b∗i = bi + c (i == L)
b∗i = bi (i != L)
当n <= L - 1 时
a∗n = ∑n1 b∗i = ∑n1 bi = an
当n >= L 时
a∗n = ∑n1 b∗i = ∑l−11 bi + (bl + c) + ∑nl+1 bi = ∑n1 bi + c = an + c
同理只需要再次构造 b∗∗n
b∗∗i = b∗i - c (i == R + 1)
b∗∗i = b∗i (i != R + 1)
当 n <= L - 1 时
a∗∗n = ∑n1 b∗∗i = ∑n1 b∗i = an
当 L <= n <= R 时
a∗∗n = ∑n1 b∗∗i = ∑n1 b∗i = an + c
当n >= R + 1 时
a∗∗n = ∑n1 b∗∗i = ∑r1 b∗i + (b∗r+1 - c) + ∑nr+2 b∗i = ∑n1 b∗i - c = a∗n - c = an + c - c = an
则 a∗∗n 为我们的目标数组,且只需要对差分数组 bn 进行以下两次操作得到
bl = bl + c
br+1 = br+1 - c
注意:
差分只能用于一次性处理完所有偏移指令,再还原。
如果是偏移和还原交错进行,就不是单独一个差分序列能高效解决的问题了。
代码实现
参考文献
https://www.acwing.com/solution/content/223661/
C++ 代码
#include <iostream>
using namespace std;
#define int long long
const int N = 1e5 + 10;
int a[N], d[N];
signed main()
{
int n, m;
cin >> n >> m;
a[0] = 0; d[0] = 0;
for(int i = 1; i <= n; ++ i)
{
scanf("%lld",&a[i]);
d[i] = a[i] - a[i-1];
}
while(m--)
{
int l, r, c;
scanf("%lld%lld%lld",&l,&r,&c);
d[l] += c;
d[r+1] -= c;
}
int sum = 0;
for(int i = 1; i <= n; ++ i)
{
sum += d[i];
printf("%lld ",sum);
}
return 0;
}