题解 | 【模板】差分

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        long[] a = new long[n + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            a[i] = Long.parseLong(st.nextToken());
        }

        long[] d = new long[n + 2];
        d[1] = a[1];
        for (int i = 2; i <= n; i++) {
            d[i] = a[i] - a[i - 1];
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int l = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());
            long k = Long.parseLong(st.nextToken());
            d[l] += k;
            if (r + 1 <= n + 1) {
                d[r + 1] -= k;
            }
        }

        long[] result = new long[n + 1];
        result[1] = d[1];
        for (int i = 2; i <= n; i++) {
            result[i] = result[i - 1] + d[i];
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            sb.append(result[i]).append(' ');
        }
        System.out.println(sb.toString().trim());
    }
}

https://www.nowcoder.com/discuss/727521113110073344

思路：

1. 输入处理：使用BufferedReader和StringTokenizer高效读取输入数据。
2. 差分数组初始化：根据初始数组构造差分数组，其中d[i] = a[i] - a[i-1]。
3. 区间修改处理：对于每个区间修改操作，更新差分数组的两个位置，时间复杂度为O(1)。
4. 前缀和计算：通过差分数组计算前缀和，得到最终的结果数组。
5. 结果输出：将结果数组转换为字符串输出。