题意整理。

• 给定一个长度为n的正整数数组，对这个数组进行m次操作，每次操作给定左右边界l、r，以及一个参数k，将数组中下标在l到r范围内所有数加上k。
• 求k次操作之后的数组。

方法一（差分数组）

1.解题思路

• 首先定义一个差分数组，在每次操作中，标记对应增量的边界。
• 在操作完成之后，遍历差分数组，作前缀和处理，即可还原出每一个位置处的增量。
• 最后将每一个数加上对应增量，输出操作之后的数组。

图解展示：

2.代码实现

import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        //存放数组元素
        int[] arr=new int[n];
        for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }
        //存放增量
        long[] delta=new long[n+1];
        //m次操作
        while(m-->0){
            int l=sc.nextInt();
            int r=sc.nextInt();
            int k=sc.nextInt();
            //进行差分处理
            delta[l]+=k;
            if(r>=n) continue;
            delta[r+1]-=k;
        }
        
        //计算对应元素增量
        for(int i=0;i<n;i++){
            delta[i+1]+=delta[i];
            System.out.print(delta[i+1]+arr[i]+" ");
        }
            
    }
}

3.复杂度分析

• 时间复杂度：如果不作差分处理，每次操作需要$r-l+1r-l+1$次循环运算，时间复杂度为$O(r-l)O(r-l)$，使用差分数组之后，只需常数次操作，时间复杂度为$O(1)O(1)$。
• 空间复杂度：需要额外大小为$n+1n+1$的差分数组，所以空间复杂度为$O(n)O(n)$。