差分的理解
a数组存放正常数列, b数组存放第i项和第i+1项的差值
正常a[i] = a[i-1] + b[i]
若在l-r间增加c
则在l+1到r的b值不会变
但b[l]会加c,因为a[l] - a[l-1]比之前多c
b[r+1]会减c,因为a[r+1] - a[r]比之前少c
C++ 代码
#include <iostream>
using namespace std;
const int N = 1e5 + 5;
int n, m;
int a[N], b[N];
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++)
{
int t;
scanf("%d", &a[i]);
b[i] = a[i] - a[i-1];
}
for(int i = 1; i <= m; i++)
{
int l, r, c;
scanf("%d%d%d", &l, &r, &c);
b[l] += c;
b[r+1] -= c;
}
for(int i = 1; i <= n; i++)
{
a[i] = a[i-1] + b[i];
printf("%d ", a[i]);
}
return 0;
}