Intuition#

核心思路：預處理前綴和陣列 prefix[i] = nums[0] + ... + nums[i-1]，查詢時 sumRange(l, r) = prefix[r+1] - prefix[l]。

• 如果每次查詢都暴力加總，時間為 O(n)，多次查詢效率低
• 前綴和預處理 O(n)，之後每次查詢只要 O(1)

Approaches#

1: 每次查詢暴力加總#

• 概念: 每次 sumRange 呼叫時遍歷 [left, right] 區間求和
• 時間複雜度: 初始化 O(1)，每次查詢 O(n)
• 空間複雜度: O(1) - 不需額外空間

class NumArray(private val nums: IntArray) {
    fun sumRange(left: Int, right: Int): Int {
        var sum = 0
        for (i in left..right) {
            sum += nums[i]
        }
        return sum
    }
}

⭐2: Prefix Sum#

• 概念: 預處理前綴和陣列，prefix[i] 代表 nums[0..i-1] 的總和，查詢時用差值計算
• 時間複雜度: 初始化 O(n)，每次查詢 O(1)
• 空間複雜度: O(n) - 前綴和陣列

class NumArray(nums: IntArray) {
    private val prefix = IntArray(nums.size + 1)

    init {
        for (i in nums.indices) {
            prefix[i + 1] = prefix[i] + nums[i]
        }
    }

    fun sumRange(left: Int, right: Int): Int {
        return prefix[right + 1] - prefix[left]
    }
}

前綴和陣列長度為 n + 1，prefix[0] = 0 作為哨兵，避免邊界判斷。

🔑 Takeaways#

• Pattern: Prefix Sum 是區間和查詢的基礎資料結構
• 關鍵技巧: prefix 多一位（n+1）的設計避免了邊界判斷；此概念可推廣到 2D（LC 304）和帶更新的版本（LC 307，需 BIT/Segment Tree）