AcWing 797. 差分
原题链接
简单
#include<iostream>
using namespace std;
const int N=100010;
int n,m;
int a[N],b[N]; // a 用于存储原数组,b 用于存储差分数组
void insert(int l,int r,int c)// 插入操作函数,用于在差分数组 b 上进行区间加法
{
b[l]+=c; //公式 // 在起始位置 l 增加 c
b[r+1]-=c; // 在终止位置 r+1 减去 c
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
// 初始化差分数组 b,使其表示原数组 a
for(int i=1;i<=n;i++) insert(i,i,a[i]); // 将原数组 a 的每个元素作为区间插入差分数组 b
while(m--) // 进行 m 次操作,每次操作对区间 [l, r] 增加 c
{
int l,r,c;
scanf("%d%d%d",&l,&r,&c);
insert(l,r,c);
}
// 计算前缀和,还原最终数组
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;
}