差分

已知前綴和 S[n], 構(gòu)造 b[n]

滿足條件: S[i] = b1 + b2 + … + b[n]

差分就是前綴和的逆運算

構(gòu)造 b[n]
理解即可, 沒有那么重要, 通過插入操作構(gòu)造 b[n]

b[1] = a[1]
b[2] = a[2] - a[1]
b[3 ]= a[3] - a[2]
...
b[n] = a[n] - a[n-1]

• b[n]稱為 S[n]的差分

• S[n]稱為 b[n]的前綴和

差分的用途

對 S數(shù)組的某個區(qū)間內(nèi)的數(shù)全部加上 c, 現(xiàn)在只需要對 b數(shù)組的 2 ~ 4個數(shù)加上 c

時間復(fù)雜度由 O(n) -> O(1)

一維數(shù)組差分

假設(shè)已經(jīng)求出來 b數(shù)組, 只要對 b數(shù)組求前綴和就可以求出原數(shù)組 S[n]

已知 b[n], 可以用 O(n) 的時間得到 S[n]

差分幫助我們處理一種操作, 在 S數(shù)組的 [l, r]區(qū)間內(nèi)加上數(shù) c. 則

1. a[l] ~ a[L-1]無影響
2. a[l] ~ a[r] 加上了 c
3. a[r=1] ~ a[n] 無影響

S數(shù)組操作后 對于 b數(shù)組的影響, 相當(dāng)于 b[l] + c, b[r + 1] - c

[題目 差分?jǐn)?shù)組]

輸入一個長度為n的整數(shù)序列。接下來輸入m個操作，每個操作包含三個整數(shù)l, r, c掀亩，表示將序列中[l, r]之間的每個數(shù)加上c蒋困。請你輸出進(jìn)行完所有操作后的序列竞帽。
輸入格式
第一行包含兩個整數(shù)n和m析显。
第二行包含n個整數(shù)穿撮，表示整數(shù)序列沈矿。
接下來m行，每行包含三個整數(shù)l肚医，r绢馍，c，表示一個操作肠套。
輸出格式
共一行舰涌，包含n個整數(shù)，表示最終序列你稚。
數(shù)據(jù)范圍
1≤n,m≤100000,
1≤l≤r≤n,
?1000≤c≤1000,
?1000≤整數(shù)序列中元素的值≤1000
輸入樣例：
6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1

代碼

import java.io.*;

public class Main {
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N = 100001;          // 數(shù)據(jù)規(guī)模為 10w
    static int[] b = new int[N];    // b數(shù)組為 arr數(shù)組的差分
    static int[] arr = new int[N];  // arr數(shù)組為 b數(shù)組的前綴和

    // 對差分?jǐn)?shù)組進(jìn)行插入操作
    private static void insert(int l, int r, int val) {
        // 可以畫圖進(jìn)行理解
        b[l] += val;
        b[r + 1] -= val;
    }

    // 程序入口
    public static void main(String[] args) throws IOException {
        // 初始化輸入數(shù)據(jù)
        String[] s = reader.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);
        String[] sArr = reader.readLine().split(" ");
        for (int i = 1; i <= n; i++)       // 注意下標(biāo)為 1
            arr[i] = Integer.parseInt(sArr[i - 1]);

        // 初始化 b數(shù)組
        for (int i = 1; i <= n; i++) {
            // 相當(dāng)于將 arr中全部看為 0, 則 b[n]中也全部都為 0, 再在其中區(qū)間 [i, i] 添加 arr[i], 求出 b[i]
            insert(i, i, arr[i]);
        }

        // m次循環(huán)操作
        while (m-- > 0) {
            String[] sIn = reader.readLine().split(" ");
            int l = Integer.parseInt(sIn[0]), r = Integer.parseInt(sIn[1]), val = Integer.parseInt(sIn[2]);
            insert(l, r, val);
        }

        // 求數(shù)組 arr插入元素后的值, 相當(dāng)于求 b[n]的前綴和
        for (int i = 1; i <= n; i++) {
            arr[i] = arr[i - 1] + b[i];
            log.write(arr[i] + " ");
        }

        // 釋放資源
        reader.close();
        log.flush();
        log.close();
    }
}