AcWing 797. 差分
原题链接
简单
#include <iostream>
using namespace std;
const int N = 100010;
int a[N], b[N]; // a为前缀和数组,b为差分数组
void insert(int b[], int l, int r, int c) { // 该函数表示在前缀和数组的l ~ r区间都加上c的操作,实际上是对差分数组操作
b[l] += c; // 该操作导致a的l及其之后的所有数加c
b[r + 1] -= c; // 该操作让r + 1及其之后的所有数减c
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
// 该操作求得是差分数组b
// 对a的l - r加上b,会导致insert
// 当l == r,也是一样的道理,即下面求b的过程
// 当然利用定义求差分数组也是一样的
// for (int i = 1; i <= n; i++) b[i] = a[i] - a[i - 1];
for (int i = 1; i <= n; i++) insert(b, i, i, a[i]);
while (m--) {
int l, r, c;
scanf("%d%d%d", &l, &r, &c);
insert(b, 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;
}
也就是说,可以不考虑如何构造差分数组b,因为可以当成对b数组进行了n次的插入操作