题目描述

y总差模板的个人理解和解释

样例

#include<bits/stdc++.h>

using namespace std;

const int N=1e6+10;

int n,m;

int a[N],b[N];//a是原数组及前缀和，b是差分数组。差分数组和原数组互为逆运算。
//在初始化时，我们可以理解为在0数组上，依次插入一个c = A[i]

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]);//第一次insert求的是a的差分数组，可以写写看看。
    //比如b是1，2，3，4，5，6
    //那么a是1，3，6，10，15，21；
    //a是b的前缀和数组，b是a的差分数组
    //这里的insert求的是a的差分数组,刚开始b数组的初始化全为0，a数组的数据题目已经给出；
    //例如第一次插入 b[1]=1，b[2]=0-1=-1;那么继续循环第二次插入，b[2]=-1+3=2,b[3]=0-3=-3;
    //继续循环b[3]=-3+6=3。如此循环可以看出，a的差分数组慢慢求出

    while(m--)//这里没什么好说的就是m个询问
    {
        int l,r,c;

        scanf("%d%d%d",&l,&r,&c);

        insert(l,r,c);//这里的插入才是为了解答题目
    }

    for(int i=1;i<=n;i++)  a[i]=a[i-1]+b[i];//这里y总为了省事，直接用的差分数组存储，我修改了下。
    //a[i]表示b数组前i个数的和，那么就是b数组前i-1个数的和加上第i个数。所以a[i]=a[i-1]+b[i];
    //注意此时求出的前缀和数组是加上数之后的前缀和数组。最后输出a[i]

    for(int i=1;i<=n;i++) printf("%d ",a[i]);
    //这里提醒一点，前缀和和差分数组下标都是从1开始，为了方便。
    return 0;

}