問題描述：

差分數組

1. 什么是差分數組？

差分數組 c 是原數組 a 的“差值表示”，其定義如下：

• c[0] = a[0]
• c[i] = a[i] - a[i-1] （i ≥ 1）

差分數組記錄了相鄰元素的差值。例如，原數組 a = [1, 3, 5, 2] 對應的差分數組為 c = [1, 2, 2, -3]。

2. 差分數組的優勢

通過差分數組，可以將區間操作轉換為兩次單點操作：

• 若要將區間 [l, r] 的所有元素增加 k，只需執行：
  • c[l] += k
  • c[r+1] -= k
    這一操作的時間復雜度為 O(1)，徹底避免了遍歷區間。

3. 還原原數組

對差分數組進行前綴和運算即可還原原數組：

• a[i] = c[0] + c[1] + ... + c[i]
  前綴和的本質是逐步累加差分值，恢復出原數組的實際數值。

---

解題思路詳解

步驟1：構建差分數組

1. 初始化差分數組 c，長度為 n+1（多一位用于處理右邊界）。
2. 根據原數組 a 的相鄰差值填充 c，確保 c[i] = a[i] - a[i-1]。

步驟2：處理區間操作

對于每個操作 [l, r, k]：

• 將 c[l] += k，表示從 l 開始的所有元素增加 k。
• 將 c[r+1] -= k，表示在 r+1 處抵消多余的 k，保證操作僅作用于 [l, r]。

步驟3：還原修改后的數組

通過前綴和還原最終的數組：

• 從 c[1] 開始，依次累加 c[i] += c[i-1]，最終 c[0...n-1] 即為修改后的原數組。

---

代碼：

public static void main(String[] args) {//通過原數組計算 差分 數組//再通過計算出的 差分 數組做 數據操作，例如（要將[l,r]區間所有數組+1）就將c[l]+1 c[r+1]-1//對差分數組，做前綴和操作得到原數組//有一個坑，雖然數據都是在int范圍內，但是會涉及到相加操作，可能會超出int范圍，所以我們的差分數組應該設置為longScanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();int[] a = new int[n];//在創建差分數組的時候長度要設置為a.length + 1這是很有必要的,防止數組越界 這個邊界操作(c[r + 1] -= 1;)long[] c = new long[n + 1];a[0] = sc.nextInt();//初始化差分數組c[0] = a[0];for (int i = 1; i < n; i++) {a[i] = sc.nextInt();c[i] = a[i] - a[i - 1];}
//        System.out.println("原數組a:" + Arrays.toString(a));
//        System.out.println("差分數組c:" + Arrays.toString(c));//要將[l,r]區間所有數組+cfor (int i = 0; i < m; i++) {int l = sc.nextInt();int r = sc.nextInt();int sum = sc.nextInt();c[l - 1] += sum;c[r] -= sum;}for (int i = 1; i < n; i++) {//這里復原的原理其實很簡單// 例如對 1 2 3 4 5的[2,4]區間做+1操作，// 由于差分數組記錄的是第i個數比第i-1個數大多少，之前i比i-1大1，+1操作之后，就是i比i-1大2了，// 但是由于我們要求在到[l,r]區間，所以r之后的差分就得還原 所以再做一個-1操作還原// 所以還原的時候，就能得到題目要求的數組了c[i] += c[i - 1];}for (int i = 0; i < n; i++) {if (c[i] < 0) {System.out.print(0 + " ");} elseSystem.out.print(c[i] + " ");}}