题目描述

差分

时间复杂度

计算为 o(1);
初始化 差分 数组 o(n);
还原操作后的 原数组 o(n);

参考文献

JAVA 代码

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

class Main{
    static int n;
    static int[] b;

     public static void insert(int l, int r, int c){
        b[l] += c;
        if(r < n)b[r + 1] -= c ;

    }

    public static void main(String args[]) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        String[] s1 = in.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        int m = Integer.parseInt(s1[1]);

        int[] a = new int[n+1];
        b = new int[n+1];

        String[] s2 = in.readLine().split(" ");
        for(int i = 1; i<= n; i++){
            //初始化 原数组
            a[i] = Integer.parseInt(s2[i-1]);
            //初始化 差分 数组 b[i] = a[i] - a[i-1]
            //原数组为 a[i] = b[1] + ...+ b[i];
            //利用 插入[某个数]函数完成初始化. 
            insert(i,i,a[i]);
        }

        while(m-->0){
            String[] s3 = in.readLine().split(" ");
            int l = Integer.parseInt(s3[0]);
            int r = Integer.parseInt(s3[1]);
            int c = Integer.parseInt(s3[2]);
            insert(l,r,c);
        }

        //最后利用差分还原成原数组. 此时还原后都带有在区间内 + 上了c
        for(int i = 1; i<= n; i++){
            b[i] = b[i] + b[i-1];
            System.out.print(b[i] + " ");
        }
    }

}