解题思路
给定原数组a, 构造b数组, 使得ai = b1 + b2 + … + bi;
要使原数组a[l, r]区间的每一个元素都加上c
使b[l] + c, b[r + 1] - c即可
算法1
C++ 代码
#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()
{
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
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);
}
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;
}