C++ 简单版本, 双数组 一个原数组, 一个差分数组
#include<iostream>
using namespace std;
constexpr int N = 1e+5 + 10;
int n,m; // n为数组的长度, m 为 操作的循环次数
int a[N], b[N]; // a为原数组, b为差分数组, 全局数组默认初始化为0, 默认就是一个差分数组的关系
void insert(int l, int r, int c) // 插入函数--》让原数组在区间 [l,r] 上加上一个常数处理
{
b[l] += c; // 对于差分数组的处理是将 b[l] += C. 由于a[i]原数组是差分数组的前缀和, 由于b[l] += c
b[r+1] -= c; // 故导致包括S[l]及其S[l]后面的数组元素均加上了c, 但由于是在区间[l,r]上进行的操作,故在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]); //构建差分数组,这里这样算是显示构建了
/*
b[1] = a[1] - a[0]
b[2] = a[2] - a[1]
b[3] = a[3] - a[2]
......
--> a[1] = b[1];
a[2] = b[1] + b[2];
a[3] = b[1] + b[2] + b[3] .....;
*/
while(m--)
{
int a, b,c;
cin >> a >> b >> c; // 输入区间 及 常数
insert(a,b,c); // 对差分数组进行操作
}
for(int i = 1; i <= n ; ++i) b[i] += b[i-1] ; // 对差分数组求前缀和得到更新后的原数组
for(int i = 1; i <= n; ++i) cout << b[i] << " ";
cout << endl;
return 0;
}
C++ 简化版本,只用一个数组
#include<iostream>
using namespace std;
constexpr int N = 1e+5 + 10;
int n,m;
int a[N]; //通过上面的代码其实一个数组即可完成
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; ++i)
{
int d;
cin >> d, a[i] += d, a[i+1] -= d;
}
while(m--)
{
int l,r,c;
cin >> l >> r >> c;
a[l] += c;
a[r+1] -= c;
}
for(int i = 1; i <= n ; ++i) a[i] += a[i-1];
for(int i = 1; i <= n; ++i) cout << a[i] <<" ";
cout <<endl;
}
注意事项