易理解版本
使用b[i]存放的插入部分的前缀
将$ O(n)$简化到$O(1)$
避免穷举
#include<iostream>
using namespace std;
const int N=100010;
int n,m;
int a[N],b[N];
void insert(int l,int r,int c)
{
b[l]+=c;
b[r+1]-=c;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];//输入原来数组
while(m--) //b[i] 存放插入的前缀和
{
int l,r,c;
cin>>l>>r>>c;
insert(l,r,c);
}
for(int i=1;i<=n;i++)
{
b[i]+=b[i-1];
a[i]=a[i]+b[i];
}
for(int i=1;i<=n;i++) cout<<a[i]<<' ';
}
差分2
#include<iostream>
using namespace std;
const int N=100010;
int n,m;
int a[N],b[N];
void insert(int l,int r,int c)
{
b[l]+=c;
b[r+1]-=c;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];//输入原来数组
for(int i=1;i<=n;i++) insert(i,i,a[i]);
while(m--)
{
int l,r,c;
cin>>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++) cout<<b[i]<<' ';
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~