题目描述

差分数组 C++

样例

// 差分数组
#include <iostream>
using namespace std;
const int N = 100010;
int q[N];
int arr[N];

int main()
{
    int m,n;
    cin >> m >> n;
    for (int i = 1; i <= m; i++)
    {
        cin >> q[i];
        // 构造差分数组
        arr[i] = q[i] - q[i - 1];
    }
    while (n-- >0)
    {
        int l, r,val;
        cin >> l >> r >> val;
        // 注意此处的等价替换
        arr[l] += val;
        arr[r + 1] -= val;
    }
    // 前缀和恢复q数组
    for (int i=1;i<=m;i++)
    {
        q[i] = q[i - 1] + arr[i];
        cout << q[i] << " ";
    }

    return 0;
}