LeetCode 303 Range Sum Query Immutable：前綴和陣列 O(1) 區間查詢

題目描述

靜態整數陣列 nums，多次查詢區間 [i, j]（含端點）元素和。陣列不變，查詢次數多（測試案例達 10000 次）。

範例

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

前綴和優化

預計算 prefix[k] = sum(nums[0..k])，則 sumRange(i, j) = prefix[j] - prefix[i-1]（i=0 時直接 prefix[j]）。

代碼實作

class NumArray {
    vector prefix;
public:
    NumArray(vector& nums) {
        prefix.resize(nums.size());
        int sum = 0;
        for (size_t i = 0; i < nums.size(); ++i) {
            sum += nums[i];
            prefix[i] = sum;
        }
    }
    
    int sumRange(int i, int j) {
        return i == 0 ? prefix[j] : prefix[j] - prefix[i-1];
    }
};

錯誤嘗試與修正

• 初版：每次查詢迴圈累加 → O(n) 查詢，**超時**（10000 次查詢 × 大陣列）。
• 改用 map 存儲前綴和 → 仍較慢（紅黑樹查找開銷）。
• 最終：vector 連續記憶體，O(1) 隨機存取，**624ms 通過**。

複雜度

關鍵點

1. 靜態區間和查詢 → 前綴和是標準解。
2. 選擇 vector 而非 map 利用緩存局部性與 O(1) 索引。
3. 處理 i=0 邊界避免越界。