題目網址：https://leetcode.cn/problems/range-sum-query-immutable/

題意：給一 array, 多次輸入不同的 left 和 right, 求 array 中從 idx = left 到 idx = right 之和。

Solution 1：

想法: 每一次 query 都去計算

class NumArray {
private:
    vector<int> nums_;

public:
    NumArray(vector<int>& nums) {
        nums_ = move(nums); // 複製 nums
    }

    int sumRange(int left, int right) {
        int sum = 0;
        for (int i = left; i <= right; ++i) {
            sum += nums_[i];
        }
        return sum;
    }
};

令 query 次數：m 次, nums 中元素個數：n

  • time：$O(m \cdot n)$ ➔ m 次 query，每次 query 需 $O(n)$ 時間
  • space：$O(n)$ ➔ nums_

Solution 2：

想法：利用 Prefix Sum, 事先計算前 i 個數之和

sums 紀錄前 i 個數之和
nums: [-2,  0, 3, -5,  2, -1]
sums: [-2, -2, 1, -4, -2, -3]

range(left, right):
    if (left == 0) { // e.g. range(0, 2)
        sum = sums[right]
    } else { // e.g. range(2, 5) -> -3 - (-2) = 1
        sum = sums[right] - sums[left-1]
    }
class NumArray {
public:
    NumArray(vector<int>& nums) {
        const int n = nums.size();
        sums = vector<int>(n, nums[0]);

        for (int i = 1; i < n; ++i) {
            sums[i] = sums[i-1] + nums[i];
        }
    }

    int sumRange(int left, int right) {
        if (left == 0) {
            return sums[right];
        }
        return sums[right] - sums[left - 1];
    }

private:
    vector<int> sums;
};

令 query 次數：m 次, nums 中元素個數：n

  • time：$O(m+n)$ ➔ $O(n)$ + $m * O(1)$
    • $O(n)$ : 計算 prefix sum 的時間
    • $m * O(1)$ : m 次 query, 每次 query 只需 $O(1)$ 時間
  • space：$O(n)$ ➔ sums