---
title: "303. Range Sum Query - Immutable"
url: "https://laigary.com/interview/coding/303-range-sum-query-immutable"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-26"
tags: ["Design", "Prefix Sum", "Array"]
---

# 303. Range Sum Query - Immutable

[303\. Range Sum Query - Immutable](https://leetcode.com/problems/range-sum-query-immutable/)

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

## 思路

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

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

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

$$
\text{sum}(l, r) = \text{preSum}(r) - \text{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` 的索引是**個數**不是位置」就不會亂。

## 解題方向

```python
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)$：

```python
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](https://leetcode.com/problems/range-sum-query-mutable/)。面試時如果對方追問「那如果陣列會被更新呢」，這就是答案。

### 相關題

[304. Range Sum Query 2D - Immutable](/interview/coding/304-range-sum-query-2d-immutable) —— 二維版，前綴和變成「左上角矩形的和」，查詢要用**容斥原理**（加一塊減兩塊再加回一塊）。

[560. Subarray Sum Equals K](/interview/coding/560-subarray-sum-equals-k) —— 前綴和的另一個經典用法：配 hash table 數「有幾個區間的和等於 k」。**看到「區間和」就先想前綴和**，這條線一路延伸到 [437. Path Sum III](/interview/coding/437-path-sum-iii)（把區間換成樹的路徑）。

## 複雜度

**前綴和**
- `__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」就該想到可以預先算好**。