NC7 【模板】差分

描述

给你一个长度为的正数数组。
接下来对这个数组进行次操作，每个操作包含三个参数，代表将数组中位置位于区间的元素都加上。
请输出操作后的数组。

输入描述：

第一行包含两个整数和。
第二行包含个整数表示。
接下来是行，每行三个整数，分别代表每次操作的参数。

参数限制：

• 
• 
• 
• 

  输出描述：

  输出1行，表示次操作后的。

解决思路：差分+数组的前缀和

• 数组的前缀和(前n项和)：prefixSum[i]表示数组nums中[0:i]范围内所有元素的和，利用动态规划prefixSum[i]=prefixSum[i-1]+nums[i]很容易算出。
• 简单差分：考虑数组[1,3,5,7,9]，
  • 假设有一组数l=2,r=3,k=+2，表明要对原数组的[5,7]分别加2；
  • 此时使用额外的数组diff（初始化为0）并记录diff[l]=diff[2]+=k=2，diff[r+1]=diff[4]+=-k=-2，也即diff=[0,0,2,0,-2]；
  • 那么diff的前缀和数组即为[0,0,2,2,0]，也就是l=2,r=3,k=+2操作后原数组各元素对应的改变量；
  • 而且这种操作是可累加的，也就是说，假设有2组操作数l=2,r=3,k=+2和l=1,r=3,k=-5，
    • 如果依次计算，则第一次操作后nums=[1,3,7,9,9]，第二次操作后nums=[1,-2,2,4,9]；
    • 使用差分和前缀和计算，第一次操作使得diff=[0,0,2,0-2]，第二次操作使得diff=[0,-5,2,0,3]；diff数组的前缀和数组为[0,-5,-3,-3,0]，加上原数组元素[1,3,5,7,9]可得结果[1,-2,2,4,9]，与原结果一致。
• 所以使用差分和前缀和计算可以将时间复杂度压缩到（O(m)是要依次计算m次操作后的diff数组，O(n)是要计算diff的前缀和数组），空间复杂度为(diff数组，并该数组上计算前缀和)。
• 暴力解法的时间复杂度为，空间复杂度为。

代码实现

#include <iostream>
#include <vector>
typedef long long DT;
using namespace std;
int main()
{
    int n, m;
    cin >> n >> m;
    vector<DT> nums(n+1, 0);
    for(int i=1; i<=n; ++i){
        cin >> nums[i];
    }
    // 计算差分数组
    vector<DT> dp_diff(n+1, 0);
    int l, r, k;
    while(--m >= 0){
        cin >> l >> r >> k;
        dp_diff[l] += k;
        if(r+1 <= n){
            dp_diff[r+1] -= k;
        }
    }
    // 计算差分数组的前缀和
    for(int i=1; i<=n; i++){
        dp_diff[i] = dp_diff[i-1] + dp_diff[i];
    }
    for(int i=1; i<=n; i++){
        cout << nums[i] + dp_diff[i] << " ";
    }
    cout << endl;
}