303. Range Sum Query - Immutable

題目描述

給定一個整數陣列 nums，實作 NumArray 類別：

• NumArray(int[] nums) — 以整數陣列 nums 初始化物件
• int sumRange(int left, int right) — 回傳 nums[left] 到 nums[right]（含兩端）的元素總和

sumRange 可能被呼叫非常多次，因此需要 O(1) 時間回答每次查詢。

解題思路

核心概念：前綴和（Prefix Sum）

若每次查詢都從 left 加到 right，時間複雜度為 O(n)，對大量查詢效率極差。

前綴和是解決區間求和問題的經典技巧：

預先建立陣列 prefix，其中 prefix[i] 代表 nums[0] + nums[1] + ... + nums[i-1]（即前 i 個元素的總和）。特別地，prefix[0] = 0（空前綴）。

建構方式：

prefix[0] = 0
prefix[1] = nums[0]
prefix[2] = nums[0] + nums[1]
...
prefix[i] = prefix[i-1] + nums[i-1]

查詢區間 [left, right] 的總和：

sumRange(left, right) = prefix[right+1] - prefix[left]

直觀解釋：prefix[right+1] 是從頭到 right 的總和，prefix[left] 是從頭到 left-1 的總和，兩者相減恰好得到 [left, right] 的總和。

這樣預處理只需 O(n) 時間，之後每次查詢只需一次減法，達到 O(1)。

時間複雜度

• 建構子 NumArray：O(n)，需要遍歷整個陣列一次來建立前綴和陣列。
• sumRange 查詢：O(1)，每次查詢只需一次陣列存取與一次減法運算。

若共有 q 次查詢，總時間為 O(n + q)，而暴力法為 O(n × q)，差距非常顯著。

空間複雜度

O(n)，額外儲存長度為 n+1 的前綴和陣列。

替代方案

方案一：暴力求和

每次 sumRange(left, right) 都從 left 累加到 right。

• 優點：不需要額外空間，程式碼極為簡單。
• 缺點：每次查詢 O(n)，若查詢次數多則效率極差，不適合本題。

方案二：快取所有可能的查詢結果

預先計算所有 (left, right) 組合的答案，存在二維陣列中。

• 優點：查詢 O(1)，與前綴和相同。
• 缺點：預處理時間 O(n²)、空間 O(n²)，當 n 很大時完全不可行，遠不如前綴和。

方案三：線段樹（Segment Tree）

建立線段樹支援區間查詢。

• 優點：同時支援點更新（單點修改後查詢仍 O(log n)），比前綴和更靈活。
• 缺點：對於本題（陣列不可變）而言，程式碼複雜度遠高於前綴和，屬於殺雞用牛刀。前綴和是本題的最優解。

延伸問題

1. 如果陣列允許更新怎麼辦？ 若 nums[i] 可以被修改，前綴和方案每次更新需要 O(n) 時間重新計算。可以使用二元索引樹（Binary Indexed Tree / Fenwick Tree），讓更新和查詢都達到 O(log n)。這就是 LC 307 Range Sum Query - Mutable 的題目。

2. 如何推廣到二維矩陣？ 將一維前綴和推廣為二維前綴和（2D Prefix Sum），可以 O(1) 回答任意子矩陣的元素總和。這就是 LC 304 Range Sum Query 2D - Immutable 的題目。

3. 前綴和能否用於非靜態問題？ 前綴和的本質是「預處理換查詢時間」，只適合靜態資料。對於需要頻繁修改的場景，應考慮線段樹（Segment Tree）或樹狀陣列（BIT），它們能在修改與查詢之間取得更好的平衡。