303. Range Sum Query - Immutable

──────────────────────────────────────────────────────────────────────

給一個不會改變的陣列，要能重複回答「區間 [left, right] 的總和是多少」。

思路

題目的關鍵字是 Immutable（不可變）和「多次查詢」。這兩個字合起來就是在說：

可以預先算好，把每次查詢的成本攤平到建構階段。

如果每次查詢都現場加總，單次是 $O (n)$ ，q 次查詢就是 $O (n q)$ 。而「區間和」有一個很好的性質可以利用：

sum (l, r) = preSum (r) - preSum (l - 1)

也就是前綴和相減。只要先花 $O (n)$ 算好每個位置的前綴和，之後每次查詢都是 $O (1)$ 的一次減法。

為什麼要多一格

前綴和陣列開 n + 1 格、preSum[0] = 0 是刻意的：這樣 sumRange(0, r) 就不用寫特例（否則 preSum[-1] 會出事）。多墊一格把邊界吃掉，是前綴和題的通用寫法。

代價是索引偏移一格：preSum[i] 代表「前 i 個元素的和」，所以查詢要寫成 preSum[right + 1] - preSum[left]。這個 +1 / 不 +1 是唯一容易寫錯的地方 —— 記住「preSum 的索引是個數不是位置」就不會亂。

解題方向

class NumArray:

    def __init__(self, nums: List[int]):
        self.preSum = [0] * (len(nums) + 1)
        for i in range(1, len(self.preSum)):
            self.preSum[i] = self.preSum[i - 1] + nums[i - 1]

    def sumRange(self, left: int, right: int) -> int:
        return self.preSum[right + 1] - self.preSum[left]

十行不到，而且 sumRange 是一行 —— 這就是「把成本移到建構階段」的價值。

補充

樹狀陣列（Binary Indexed Tree）

如果陣列會被修改，前綴和就失效了（改一個元素要重算後面全部， $O (n)$ ）。那時候要用樹狀陣列，它讓「單點更新」和「前綴查詢」都變成 $O (\log n)$ ：

class BIT:
    def __init__(self, n: int):
        self.sums = [0] * (n + 1)

    def lowbit(self, i: int):
        return i & -i

    def update(self, i:int , delta: int):
        while i < len(self.sums):
            self.sums[i] += delta
            i += self.lowbit(i)

    def query(self, i: int) -> int:
        res = 0
        while i > 0:
            res += self.sums[i]
            i -= self.lowbit(i)
        return res

class NumArray:

    def __init__(self, nums: List[int]):
        self.nums = nums
        self.tree = BIT(len(nums))
        for i in range(len(self.nums)):
            self.tree.update(i + 1, nums[i])

    def sumRange(self, left: int, right: int) -> int:
        return self.tree.query(right + 1) - self.tree.query(left)


# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(left,right)

lowbit(i) = i & -i 取出 i 最低位的那個 1，它決定了每個節點負責管多長的區間。update 往上走（i += lowbit）、query 往回走（i -= lowbit），兩個方向都是每次至少去掉一個二進位位，所以是 $O (\log n)$ 。

這題用樹狀陣列是殺雞用牛刀 —— 陣列不會變，前綴和已經是最優。寫在這裡是為了對照，真正需要它的是 307. Range Sum Query - Mutable。面試時如果對方追問「那如果陣列會被更新呢」，這就是答案。

複雜度

前綴和

__init__ 時間 $O (n)$ — 一趟累加
sumRange 時間 $O (1)$ — 一次減法
空間 $O (n)$ — 前綴和陣列

樹狀陣列

__init__ 時間 $O (n \log n)$ — n 次 update，每次 $O (\log n)$
sumRange 時間 $O (\log n)$ — 兩次 query
空間 $O (n)$

其中 n 是陣列長度。

這題的正解是前綴和：建構更快、查詢更快、程式碼更短。樹狀陣列唯一贏的地方是支援更新 —— 而這題的題目名稱已經寫了 Immutable，所以不需要。讀題時看到「immutable」就該想到可以預先算好。

303. Range Sum Query - Immutable

思路

為什麼要多一格

解題方向

補充

樹狀陣列（Binary Indexed Tree）

相關題

複雜度