差分数组

对于一个数组A[N]， 其查分数组D[i] = A[i] - A[i - 1] (i > 0 && D[0] = A[0])

给定数组　　A[8] = {0, 1, 2, 3,  1,  0,  0, 0}

其差分数组    D[8] = {0, 1, 1, 1, -2, -1, 0, 0}

数组D的前n项前缀和 sigmaDn = D0 +  D1 + ... + Dn， 根据上述公式展开化简后得: sigmaDn = An

不难发现原数组就是差分数组的前缀和数组

如果我们让D[left] + C， 那么我们就相当于对从A[i]开始的包括A[i]在内的后面的所有元素都加了C。比如让D[4]+1就相当于A[4...7]全部+1

如果想让A[left, right]内所有元素+1，只需要让D[left]+1, D[right]-1即可

例题：https://www.acwing.com/problem/content/738/

#include <iostream>
using namespace std;

constexpr int N = 100'005;
int d[N], a[N];
int n, q, l, r;
int main() {
    cin >> n >> q;
    while (q--) {
        cin >> l >> r;
        d[l]++, d[r + 1]--;
    }
    
    for (int i = 1; i <= n; ++i) {
        a[i] = a[i - 1] + d[i];
        cout << a[i] << ' ';
    }
    
    return 0;
}