题目描述

题目：就是给定一个一维数组,然后让对应的[l,r]区间加上某个数值,最后再把这个数组输出.

输入样例

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

输出样例

3 4 5 3 4 2

算法1

(暴力枚举) $O(n^2)$

思路：就是每次让对应的[l,r]区间加上某个数值的时候,就从l到r遍历一下数组加上相应的数值.这样的话如果n次加减,每次加减都是从1到数组的最后一位,那么时间复杂度就是$O(n^2)$,good!

时间复杂度 $O(n^2)$

参考文献：me

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static final int N = 100010;
    public static int n,m;
    public static int[] a = new int[N];
    public static int[] b = new int[N];

    public static void main(String[] args) throws IOException {
        BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));
        String[] str_01 = scan.readLine().split(" ");
        n = Integer.parseInt(str_01[0]);
        m = Integer.parseInt(str_01[1]);

        // 接受a数组
        String[] str_02 = scan.readLine().split(" ");
        for (int i = 1; i <= n; i++) a[i] = Integer.parseInt(str_02[i - 1]);


        // 加减操作
        for (int i = 1; i <= m; i++){
            String[] str_03 = scan.readLine().split(" ");
            int l = Integer.parseInt(str_03[0]);
            int r = Integer.parseInt(str_03[1]);
            int c = Integer.parseInt(str_03[2]);
            for (int j = l; j <= r; j++) a[j] += c;
        }

        for (int i = 1; i <= n; i++){
            if (i == n) System.out.print(a[i]);
            else System.out.print(a[i] + " ");
        }

    }
}

算法2

(差分) $O(n)$

差分概念：既然我们已经发现用暴力的话有问题,那我们想一下应该怎么优化,这时候差分就出现了,先说说什么是差分数组,假如说有一个数组a[1,2,3,4,5],差分数组就是求a的每一位的前缀和,比如a[1] = 1(下标从1开始),那他的前缀和就是b[1] = 1(用b代表差分数组),再比如a[2] = 2,那他的前缀和就是b[2] = a[2] - b[1] = 1;类似这样b就是a的差分数组.(b==>[1,1,1,1,1])

思路：现在我们知道了差分数组,那在求a的[2,3]区间加上1的时候,是不是就可以让b的第二个位置+1,然后第3+1个位置-1,此时b==>1,2,0,1,1,如果只+1不减去1的话(b==>[1,2,1,1,1]),求a[4]的时候就多加了一个1,eg:a[4] = b[1] + b[2] + b[3] + b[4] = 5,a[5] = 6了,都多加了一个1所以要减去1.现在我们解决了这个问题,并且每次都用的加减,则时间复杂度是$O(1)$,整体的时间复杂度就是$O(n)$

时间复杂度：$O(n)$

参考文献：y总

Java 代码

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main{
    public static final int N = 100010;
    public static int n,m;
    public static int[] a = new int[N];
    public static int[] b = new int[N];

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

    public static void main(String[] agrs) throws IOException{
        BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));
        String[] str_01 = scan.readLine().split(" ");
        n = Integer.parseInt(str_01[0]); m = Integer.parseInt(str_01[1]);

        String[] str_02 = scan.readLine().split(" ");
        for (int i = 1; i <= n; i++) a[i] = Integer.parseInt(str_02[i - 1]); // 接受数组
        for (int i = 1; i <= n; i++) insert(i, i, a[i]); // 构造a的差分数组

        for (int i = 1; i <= m; i++){
            String[] str_03 = scan.readLine().split(" ");
            int l = Integer.parseInt(str_03[0]); int r = Integer.parseInt(str_03[1]); int c = Integer.parseInt(str_03[2]);
            insert(l, r, c);// 对差分数组进行对应操作
        }

        for (int i = 1; i <= n; i++) b[i] += b[i - 1]; // 把差分数组还原成a
        for (int i = 1; i <= n; i++){
            if (i == n) System.out.print(b[i]);
            else System.out.print(b[i] + " ");

        }
    }
}