C语言：差分

【模板】差分_牛客题霸_牛客网 (nowcoder.com)

??

?上图中[1,2]+4==d[0]+4,d[1]+4,d[2]+4,d[3]+4...d[2]-4,d[3]-4...

? ? ? ? ? ? ?[3,3]-2==d[2]-2,d[3]-2,d[4]-2....d[3]+2,d[4]+2...

通过求前缀和操作，相当于用另一个数组完成了差分操作，再将原数组加上该数组，即可得到答案。

#include<stdio.h>
#define ll long long
ll a[100005];//存储数组
ll d[100005] = {0};//作为差分数组
void arr(ll l, ll r, ll k)
{
	d[l] += k;
	d[r + 1] -= k;
}
int main()
{
	ll n = 0;
	ll m = 0;
	scanf("%lld %lld", &n, & m);
	for (ll i = 0; i < n; i++)
	{
		scanf("%lld", &a[i]);//输入数组
	}
	ll l = 0;//第一个前缀
	ll r = 0;//第二个前缀
	ll k = 0;//操作数
	for (ll i = 0; i < m; i++)
	{
		scanf("%lld %lld %lld", &l, &r, &k);
		arr(l - 1, r - 1, k);
	}
	for (ll i = 1; i < n; i++)
	{
		d[i] += d[i - 1];//
	}
	for (ll i = 0; i < n; i++)
	{
		a[i] += d[i];//原数组加上差分数组
	}
	for (ll i = 0; i < n; i++)
	{
		printf("%lld ", a[i]);//打印数组
	}
	return 0;
}