补充知识

定义

首先给定一个原数组a[i]，如果存在有另一个数组b[i],且a[i]=b[1]+b[2]+b[3]+...b[i],那么a数组是b数组的前缀和数组，反过来称b为a的差分数组。简单来说，每一个a[i]都是b数组从头到i的区间和。

规律

在知道b数组是a数组的差分数组的前提下，对差分数组的一个元素b[i]的修改，会影响到前缀和数组a中的a[i]及之后的每个元素的值

根据上述图示我们可以得出

• b[i]+c时，a数组变成a[i] + c ,a[i+1] + c ... a[i+n] + c

• b[i]-c时，a数组变成a[i] - c ,a[i+1] - c ... a[i+n] - c

启发

给定区间[l ,r ]，让我们把a数组中的   [l ,r ]区间中的每一个数都加上c,即 a[l] + c, a[l+1] + c, a[l+2] + c ... a[r] + c;暴力做法是for循环l到r区间，时间复杂度O(n)，如果我们需要对原数组执行m次这样的操作，时间复杂度就会变成O(n*m)。有没有更高效的做法吗?

此时根据前文内容，我们就可以很轻松的知道，给a数组中的[l, r]区间中的每一个数都加上c,只需对差分数组b做 b[l] + = c, b[r+1] - = c，配合下图食用更好理解（红色区域为代表给a数组中的元素都+c,绿色区域代表给a数组中的元素-c）,如此一来，r+1部分(绿色区域和红色区域互相抵消了）的操作去除后就可以得出l,r区间的结果。

如何构造差分数组

我们知道，数组a为b的前缀和数组，那么b[i]就应该等于a[i]-a[i-1],所以我们可以采用b[i] = a[i] - a[i - 1]这个式子构造出差分数组b[i]

具体问题

输入一个长度为 n 的整数序列。

接下来输入 m 个操作，每个操作包含三个整数 l,r,c，表示将序列中 [l,r] 之间的每个数加上 c。

请你输出进行完所有操作后的序列。

输入格式

第一行包含两个整数 n 和 m。

第二行包含 n 个整数，表示整数序列。

接下来 m 行，每行包含三个整数 l，r，c，表示一个操作。

输出格式

共一行，包含 n 个整数，表示最终序列。

数据范围

1≤n,m≤100000,
1≤l≤r≤n,
−1000≤c≤1000,
−1000≤整数序列中元素的值≤1000

输入样例：

6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1

输出样例：

3 4 5 3 4 2

AC代码

import java.io.*;
import java.util.*;
public class Main{

    public static void main(String [] args)throws IOException{
        //数组范围
        int N =100010;
        BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
        String[] line=in.readLine().split(" ");
        int n=Integer.parseInt(line[0]);
        int m=Integer.parseInt(line[1]);
        int [] a=new int[N];
        int [] b=new int[N];
        String[] tmp=in.readLine().split(" ");
        for(int i=1;i<=n;i++){
            a[i]=Integer.parseInt(tmp[i-1]);
            //构造差分数组
            b[i]=a[i]-a[i-1];
        }
        while(m-->0){
            //输入l,r,c
            String[] tmp2=in.readLine().split(" ");
            int l=Integer.parseInt(tmp2[0]);
            int r=Integer.parseInt(tmp2[1]);
            int c=Integer.parseInt(tmp2[2]);

            //将序列中[l,r]每个数都加上c
            b[l]+=c;
            b[r+1]-=c;
        }
        //还原变化后的a数组
        for(int i=1;i<=n;i++){
            a[i]=b[i]+a[i-1];
            System.out.print(a[i]+" ");
        }       
    }        
}