题目:
输入一个长度为 n 的整数序列。
接下来输入 m 个操作,每个操作包含三个整数 l,r,c,表示将序列中 [l,r]之间的每个数加上 c。
请你输出进行完所有操作后的序列。
/*
差分
若数组A:a1,a2,a3
数组B:b1,b2,b3
满足a1 = b1
a2 = b1 + b2
a3 = b1 + b2 + b3
即b(n) = a(n) - a(n-1),a(0) = 0
就称数组B是数组A的差分数组
数组A是数组B的前缀和数组
差分和前缀和互为逆运算
对于本题,对原数组A的区间[l, r] 上的数都加上c的时间复杂度为O(n)
如果对A的差分数组B进行操作只需要让B[l] += c; B[r+1] -= c; 时间复杂度为O(1),加快了速度,空间换时间
*/
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int a[N], b[N];
//对原数组A的差分数组B先进行操作
void insert(int l, int r, int c)
{
b[l] += c;
b[r + 1] -= c;
}
int main()
{
a[0] = 0;
b[0] = 0;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
//初始化差分数组
//b(n) = a(n) - a(n-1)
for(int i = 1; i <= n; i++) insert(i, i, a[i]);
while(m--)
{
int l, r, c;
scanf("%d%d%d", &l, &r, &c);
insert(l, r, c);
}
//将数组B直接变成数组A的前缀和
for(int i = 1; i <= n; i++) b[i] += b[i - 1];
//输出
for(int i = 1; i <= n; i++) printf("%d ", b[i]);
return 0;
}