算法
时间复杂度 $O(n)$
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, m,f[N],s[N];
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++) scanf("%d", &f[i]);
for(int i = 1; i <= n; i++) s[i] = f[i] - f[i - 1];
while(m--){
int l, r, c;
cin >> l >> r >> c;
s[l] += c;
s[r + 1] -= c;
}
for(int i = 1; i <= n; i++){
f[i] = f[i - 1] + s[i];
cout << f[i] << ' ';
}
cout << endl;
return 0;
}
分析
主要我觉得差分和前缀和部分这种写法最好记,记一条公式就行了$s[i]=f[i]-f[i-1]$