差分数组

可以利用差分数组在o(1)的时间复杂度内将区间内的元素都加上某个数。

例如

输入一个长度为 n 的整数序列。接下来输入 m 个操作，每个操作包含三个整数 l,r,c，表示将序列中 [l,r] 之间的每个数加上 c。
请你输出进行完所有操作后的序列。
原题链接

讲解

• 加入原数组是a[n],差分数组是b[n]，差分数组的前缀和就是a[n]，比如说差分数组的前两项和就是a[2]，没有听懂的看下方的题解。
  
• 我们如何实现在区间内加上一个数呢？
  加入区间是l、r，我们在原数组的差分数组b[l]加上个xb[l] += x，然后再b[r+1]减去个xb[r + 1] -= x。
  看图，假如我们要让a[2]到a[4]都要加上x，我们在b[2]加上x因为差分数组的前缀和是原数组，所以导致a[2]到最后都会加上x，因为我们要到a[4]，所以a[5]到最后不用加上x，所以要在b[5]减去x，这样a[5]到最后都会减去x，先加x后减x相当于不变(a[5]到最后)。
  换一种说法，a[2] = b[1] + b[2]，因为b[2]加了个x，所以a[2]也加了个x,同理a[3]也是加了个x。
  

总结

在原数组的差分数组的第i位加上x，区间i到最后的原数组元素都会加上x,同理减法也是。

源码

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int a[N], b[N];

void insert(int l, int r, int x)
{
    b[l] += x;
    b[r + 1] -= x;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    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;
        insert(l, r, c);
    }

    for (int i = 1; i <= n; i ++) b[i] += b[i - 1];

    for (int i = 1; i <= n; i ++ ) cout << b[i] << " \n"[i == n];

    return 0;
}