Prefix Sums

前綴和是「預處理換查詢」的代表技法：先花 O(n) 算好「從頭到每個位置的累積和」，之後任何「子陣列區間和」都能在 O(1) 內回答。看到題目反覆詢問不同區間的和（或積、或計數），就該想到它。

核心：區間和 O(1) 查詢

定義 prefix[i] 為前 i 個元素的和（prefix[0] = 0），則子陣列 nums[l..r]（含兩端）的和為：

sum(l, r) = prefix[r + 1] - prefix[l]

class PrefixSum(nums: IntArray) {
    // prefix[i] = nums[0] + ... + nums[i-1]，多開一格省去邊界判斷
    private val prefix = IntArray(nums.size + 1)

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

    // 回傳 nums[l..r] 的和（閉區間），O(1)
    fun query(l: Int, r: Int): Int = prefix[r + 1] - prefix[l]
}

前綴和 + Hash Map：和為 k 的子陣列

當問題不是「查某個固定區間」，而是「有幾個子陣列的和等於 k」時，把前綴和丟進 Hash Map 是經典套路。

關鍵恆等式：子陣列 nums[i..j] 和為 k，等價於 prefix[j+1] - prefix[i] = k，即 prefix[i] = prefix[j+1] - k。於是邊走邊用 Map 記錄「每個前綴和出現幾次」，對當前前綴和 cur 查 cur - k 出現過幾次即可。

fun subarraySum(nums: IntArray, k: Int): Int {
    val count = HashMap<Int, Int>()
    count[0] = 1            // 空前綴：和為 0 出現一次
    var cur = 0
    var ans = 0
    for (x in nums) {
        cur += x
        ans += count.getOrDefault(cur - k, 0)
        count[cur] = count.getOrDefault(cur, 0) + 1
    }
    return ans
}

變體：前綴積

把「和」換成「積」就是前綴積，常用於「除自身以外的乘積」這類題：用左前綴積乘右後綴積，避開除法（也能處理含 0 的情況）。

fun productExceptSelf(nums: IntArray): IntArray {
    val n = nums.size
    val res = IntArray(n) { 1 }
    var left = 1
    for (i in 0 until n) {        // res[i] 先存「左側所有元素的積」
        res[i] = left
        left *= nums[i]
    }
    var right = 1
    for (i in n - 1 downTo 0) {   // 再乘上「右側所有元素的積」
        res[i] *= right
        right *= nums[i]
    }
    return res
}

何時用

• 多次查詢不同區間的和／積 → 預處理前綴陣列。
• 計數「滿足某和條件的子陣列數量」 → 前綴和 + Hash Map。
• 二維版本（子矩陣和）→ 二維前綴和，查詢一樣 O(1)。

跨倉庫導讀

• 對應理論章節：線性資料結構、雜湊與散列