题解 | 【模板】差分

这一题如果直接用for循环暴力做有一个测试点会 超时

建议使用差分数组来做

我们需要创建一个数组用来表示原数组每一个元素与其前一个元素之间的关系

这个数组的长度得是n+1，这样第l个数就是索引l了

当改变l到r范围的数，c[l]+=k，c[r+1]-=k，这里需要注意的是，要判断r+1还在不在数组中，如果不在就不用执行这一步

最后我们就得到了最终每相邻两个元素之间的关系

我们可以从0开始，累加，输出即可

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner=new Scanner(System.in);
		int n=scanner.nextInt();
		int m=scanner.nextInt();
		long a[]=new long[n+1];
		long c[]=new long[n+1];
		for (int i = 1; i < a.length; i++) {
			a[i]=scanner.nextLong();
			c[i]=a[i]-a[i-1];
		}
		while(m-->0) {
			int l=scanner.nextInt();
			int r=scanner.nextInt();
			int k=scanner.nextInt();
			c[l]+=k;
			if(r+1<=c.length-1) {
				c[r+1]-=k;
			}
			
		}
		long sum=0;
		for (int i = 1; i < a.length; i++) {
			sum=sum+c[i];
			System.out.print(sum+" ");
		}

	}

}