解題說明
題目描述
給定長度為 n 的陣列（初始值全為 0），以及 k 個更新操作，每個操作為 [startIndex, endIndex, inc]，代表將陣列索引 [startIndex, endIndex] 的所有元素都加上 inc。
完成所有操作後，回傳最終陣列。
範例：n=5, operations = [[1,3,2],[2,4,3],[0,2,-2]]
- 初始：[0, 0, 0, 0, 0]
- [1,3,2]：[0, 2, 2, 2, 0]
- [2,4,3]：[0, 2, 5, 5, 3]
- [0,2,-2]：[-2, 0, 3, 5, 3]
解題思路
核心思路：差分陣列（Difference Array）
暴力解法是對每個操作遍歷 [startIndex, endIndex] 並逐一更新，時間複雜度 O(n × k)，效率低。
差分陣列是處理「區間批量修改」的經典技巧，時間複雜度降至 O(n + k)：
定義差分陣列 diff[i] = result[i] - result[i-1]（result[-1] = 0）。對區間 [l, r] 加 val 等價於：
diff[l] += val（從 l 開始增加）diff[r+1] -= val（在 r+1 處撤銷增加）
最後對差分陣列做前綴和還原，即可得到最終結果：
result[i] = diff[0] + diff[1] + ... + diff[i]
為什麼差分陣列有效？
每個操作只修改兩個位置（O(1)），而不是整個區間（O(n)）。k 個操作後，前綴和一次性還原所有修改。
直觀理解：diff[l] += val 代表「從 l 開始，後綴全部加 val」，diff[r+1] -= val 代表「從 r+1 開始，後綴全部減 val」，兩者疊加效果恰好是「區間 [l,r] 加 val」。
C++ 解法
複雜度分析
時間複雜度
O(n + k)，其中 n 為陣列長度，k 為操作次數。
- 處理 k 個操作：每個操作 O(1)，共 O(k)。
- 前綴和還原：O(n)。
- 總計：O(n + k)，遠優於暴力的 O(n × k)。
空間複雜度
O(n)，需要差分陣列（或直接在結果陣列上操作）。不計算輸出陣列本身的話，額外空間為 O(1)（原地版本）。
虛擬碼
1. Initialize diff array of size (n+1) to all zeros 2. For each update [l, r, val]: a. diff[l] += val b. diff[r+1] -= val 3. Initialize result array of size n 4. Set running = 0 5. For i from 0 to n-1: a. running += diff[i] b. result[i] = running 6. Return result
其他解法
替代方案
方案一：暴力逐元素更新
對每個操作 [l, r, val]，用迴圈將 result[l] 到 result[r] 都加上 val。
- 優點：實作極為簡單，無需理解差分陣列。
- 缺點：時間複雜度 O(n × k)，當 n 和 k 都很大時（如 n=100000, k=100000）效率完全不可接受。
方案二：線段樹（Lazy Propagation）
使用帶懶惰標記的線段樹，支援 O(log n) 的區間更新和 O(log n) 的點查詢。
- 優點：若需要在操作過程中即時查詢某個位置的值，線段樹非常適合；適合在線（online）處理。
- 缺點：對於本題（所有操作先批量進行，再一次輸出全部結果）屬於過度設計，程式碼複雜度高，常數因子大；差分陣列的 O(n + k) 整體更優。
方案三：二元索引樹（Fenwick Tree）
支援區間加法和前綴和查詢，利用兩個 BIT 可以實作 O(log n) 的區間修改和 O(log n) 的單點查詢。
- 優點：比線段樹程式碼略短，支援動態查詢。
- 缺點：同樣對本題屬於過度設計，差分陣列方案已是最佳選擇。
延伸思考
延伸問題
-
二維差分陣列：若問題從一維推廣到二維——對矩形子矩陣批量加值，如何設計差分陣列？定義
diff[i][j]的二維差分，對矩形(r1,c1)到(r2,c2)加 val：diff[r1][c1] += val,diff[r1][c2+1] -= val,diff[r2+1][c1] -= val,diff[r2+1][c2+1] += val；最後做二維前綴和還原。 -
線上查詢（online query）：本題中所有操作批量完成再查詢。若需要在每次操作後立即查詢某位置的值，差分陣列無法直接支援，應改用線段樹（Lazy Propagation）或樹狀陣列（BIT）的區間加點查詢模式。
-
差分陣列與前綴和的對偶關係：前綴和的逆操作是差分（
diff[i] = arr[i] - arr[i-1]），對差分陣列做前綴和可還原原陣列。理解這個對偶關係有助於解決 LC 1094（Car Pooling）、LC 1109（Corporate Flight Bookings）等時間序列資源分配問題。