算法基础课题解合集

什么是差分

差分指快速的在 $[l, r]$ 之内加上 $c$ 的操作。

差分的实现

我们可以建立一个 $B$数组，由于题目最后要求前缀和，所以我们其实并不用给每个数都加 $c$，而是将 $B_l + c$ 且将 $B_{r + 1} - c$

最后求一遍前缀和即可。

但是为什么是对的呢？

我们先看这两个操作执行后会发生什么。

$B_l + c$，在最后求前缀和时就是将 $A_l, A_{l + 1}, \dots, A_n$ 都 $+c$。

$B_{r + 1} - c$ 就是将 $A_{r + 1}, A_{r + 2}, \dots, A_n$ 都 $-c$。

我们可以发现，$A_l$ 到 $A_r$ 都加上了 $c$，而 $A_{r + 1}$ 到 $A_n$ 加了一个 $c$，又减了一个 $c$，所以正确性是显然的。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

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;
}

好了，这篇题解到这里就结束啦！感谢观看！！！

$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\mathcal{writer\enspace by \enspace acwing}$ : $\mathfrak{天元之弈}$