LeetCode 區間和查詢：前綴和預處理 O(1) 查詢

題目描述

給定整數數組 nums，多次查詢區間 [i, j]（i ≤ j）的元素和。數組構造後不變。

範例：

nums = [-2, 0, 3, -5, 2, -1]
sumRange(0, 2) → 1
sumRange(2, 5) → -1
sumRange(0, 5) → -3

解題思路：前綴和數組

構造函數中預計算前綴和 sums[k] = nums[0] + ... + nums[k]，查詢時：

sumRange(i, j) = sums[j] - (i > 0 ? sums[i-1] : 0)

預處理 O(n)，單次查詢 O(1)，空間 O(n)。

C++ 參考實現

class NumArray {
public:
    NumArray(vector& nums) {
        if (nums.empty()) return;
        sums.push_back(nums[0]);
        for (int i = 1; i < nums.size(); ++i) {
            sums.push_back(sums.back() + nums[i]);
        }
    }
    
    int sumRange(int i, int j) {
        if (i == 0) return sums[j];
        return sums[j] - sums[i - 1];
    }
    
private:
    vector sums;
};

Python 參考實現

class NumArray:
    def __init__(self, nums):
        self.sums = [0] * (len(nums) + 1)
        for i, num in enumerate(nums):
            self.sums[i + 1] = self.sums[i] + num
    
    def sumRange(self, i, j):
        return self.sums[j + 1] - self.sums[i]

# 測試
if __name__ == "__main__":
    obj = NumArray([-2, 0, 3, -5, 2, -1])
    assert obj.sumRange(0, 2) == 1
    assert obj.sumRange(2, 5) == -1
    assert obj.sumRange(0, 5) == -3
    print("測試通過")

核心要點總結

• 空間換時間：O(n) 空間換取 O(1) 查詢，適合「構建一次、查詢多次」場景
• 前綴和定義：sums[i] 存前 i 項和（長度 n+1，sums[0]=0）邊界處理最簡潔
• 變體延伸：二維前綴和（矩陣區域和）、可更新版（線段樹/樹狀數組）

前綴和是區間查詢問題的基石技術，掌握其「預處理 + 差分」核心模式，可高效解決大量區間聚合問題。