差分

相关题目

输入一个长度为 nn 的整数序列。

接下来输入 mm 个操作，每个操作包含三个整数 l,r,cl,r,c，表示将序列中 [l,r][l,r] 之间的每个数加上 cc。

请你输出进行完所有操作后的序列。

输入格式

第一行包含两个整数 nn 和 mm。

第二行包含 nn 个整数，表示整数序列。

接下来 mm 行，每行包含三个整数 l，r，cl，r，c，表示一个操作。

输出格式

共一行，包含 nn 个整数，表示最终序列。

数据范围

1≤n,m≤1000001≤n,m≤100000,
1≤l≤r≤n1≤l≤r≤n,
−1000≤c≤1000−1000≤c≤1000,
−1000≤整数序列中元素的值≤1000−1000≤整数序列中元素的值≤1000

输入样例：

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

输出样例：

1	3 4 5 3 4 2

算法思想

差分可以用于计算其中任意一段数组的加减，并且每次加减时间控制在O(1)
差分是前缀和的逆运算（前缀和是预先知道a[n],后计算S[n],以达到可以在O(1)时间段内，计算任意一段数据的和的目的）
前置条件：假设原来给定数组为S[n]（或自己计算出S[n]）,则计算差分数组可以为**a[n] = S[n]-S[n-1]**。
计算基础：计算让原来的素组任意一段加减一个常数c，相当于S[l~r]-c
核心计算：要知道某一段前缀和数据S[l~r]突然全部加了相同的一个数，可以被看做a[n]中的一个数据加了c而导致的连锁效应，而且S[0 ~ l-1]，S[r+1~~n]两段数据值没有改变，那我们就可以把**S[l~~r]+c**这个过程简化为 a[l]+c， a[r+1]-c，这样复杂度就瞬间见下降。

笔者代码

import java.util.Scanner;
/**一维差分
 * 给某一段加上数值*/
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        //输入si
        int[] si = new int[n+1];
        for (int i = 1; i <= n; i++) {
            si[i] = scanner.nextInt();
        }

        //计算ai = s[i]-s[i-1]
        int[] ai = new int[n+1];
        for (int i = 1; i <= n ; i++) {
            ai[i] = si[i] -si[i-1];
        }

        //由题可知s[l~r]+c = c+bl+......+br不影响s[l]之前
        //为了不影响s[r]之后的前缀和数值，我们将b[r+1]-c
        //则s[l~r]可以简化为 b[l]+=c,b[r]-=c
        int l,r,c;
        while(m-->0){
            l = scanner.nextInt();
            r = scanner.nextInt();
            c = scanner.nextInt();

            ai[l] += c;
            if(r<n){
                ai[r+1] -= c;
            }

        }

        //更新si
        for (int i = 1; i <= n; i++) {
            si[i] = ai[i] + si[i-1];
            System.out.print(si[i] + " ");
        }
    }
}