解題說明
題目描述
給定一個整數陣列 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)。
C++ 解法
複雜度分析
時間複雜度
- 建構子
NumArray：O(n)，需要遍歷整個陣列一次來建立前綴和陣列。 sumRange查詢：O(1)，每次查詢只需一次陣列存取與一次減法運算。
若共有 q 次查詢，總時間為 O(n + q)，而暴力法為 O(n × q)，差距非常顯著。
空間複雜度
O(n)，額外儲存長度為 n+1 的前綴和陣列。
虛擬碼
Constructor NumArray(nums): 1. Create prefix array of size n+1, initialized to 0 2. For i from 0 to n-1: a. prefix[i+1] = prefix[i] + nums[i] sumRange(left, right): 1. Return prefix[right+1] - prefix[left]
其他解法
替代方案
方案一：暴力求和
每次 sumRange(left, right) 都從 left 累加到 right。
- 優點：不需要額外空間，程式碼極為簡單。
- 缺點：每次查詢 O(n)，若查詢次數多則效率極差，不適合本題。
方案二：快取所有可能的查詢結果
預先計算所有 (left, right) 組合的答案，存在二維陣列中。
- 優點：查詢 O(1)，與前綴和相同。
- 缺點：預處理時間 O(n²)、空間 O(n²)，當 n 很大時完全不可行，遠不如前綴和。
方案三：線段樹（Segment Tree）
建立線段樹支援區間查詢。
- 優點：同時支援點更新（單點修改後查詢仍 O(log n)），比前綴和更靈活。
- 缺點：對於本題（陣列不可變）而言，程式碼複雜度遠高於前綴和，屬於殺雞用牛刀。前綴和是本題的最優解。
延伸思考
延伸問題
-
如果陣列允許更新怎麼辦？ 若
nums[i]可以被修改，前綴和方案每次更新需要 O(n) 時間重新計算。可以使用二元索引樹（Binary Indexed Tree / Fenwick Tree），讓更新和查詢都達到 O(log n)。這就是 LC 307 Range Sum Query - Mutable 的題目。 -
如何推廣到二維矩陣？ 將一維前綴和推廣為二維前綴和（2D Prefix Sum），可以 O(1) 回答任意子矩陣的元素總和。這就是 LC 304 Range Sum Query 2D - Immutable 的題目。
-
前綴和能否用於非靜態問題？ 前綴和的本質是「預處理換查詢時間」，只適合靜態資料。對於需要頻繁修改的場景，應考慮線段樹（Segment Tree）或樹狀陣列（BIT），它們能在修改與查詢之間取得更好的平衡。