代码
//
// Created by Genes on 2020/12/1.
//
// 一维差分
#include <iostream>
#define ios \
ios::sync_with_stdio(false); \
cin.tie(nullptr); \
cout.tie(nullptr)
using namespace std;
const int N = 1e5 + 10;
int n, m;
int a[N], b[N];
int main() {
ios;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
b[i] = a[i] - a[i - 1];
}
while (m--) {
int l, r, c;
cin >> l >> r >> c;
b[l] += c;
b[r + 1] -= c;
}
for (int i = 1; i <= n; i++) {
b[i] = b[i - 1] + b[i];
if (i > 1) {
cout << " ";
}
cout << b[i];
}
cout << endl;
return 0;
}
666666
害还是没看懂为啥差分就能O(1)
要给[l,r]这段区间+c的话, 如果是暴力, 就得每个数都+c-> O(N);
如果是求得了差分数组得话, 给[l,r]这段区间+c, 就相当于是 b[l]+c, b[r+1]-c —> O(1), 这里才两个操作,因此可以把这个操作看作是O(1), 整个题目得时间复杂度还是O(N), 因为构造差分数组就需要O(N)。 差分数组求原序列实际上就是对差分数组求前缀和 原序列—构造差分数组-> 差分数组 差分数组—求前缀和–> 结果序列