307. Range Sum Query

解法已隱藏 — 先讀題目敘述、自己想想看，再點上方按鈕揭曉。

307Range Sum Query - MutableArrays & HashingMediumArrays & Hashing

實作 NumArray：支援 update(index, val) 單點更新、sumRange(left, right) 區間和查詢，兩者都要高效（多次交錯呼叫）。

Example:

NumArray([1,3,5]) sumRange(0,2) → 9 update(1,2) // 變成 [1,2,5] sumRange(0,2) → 8

Intuition

TIP

核心思路：純前綴和能 O(1) 查詢但更新要 O(n)；改用樹狀數組（BIT），更新與查詢都 O(log n)，達到平衡。

純前綴和（303 的解）查詢 O(1)、但每次 update 要重算後續，O(n) 不划算
BIT（Fenwick）用 i & (-i) 取最低位 1，跳著維護部分和
update 與 prefix 查詢都沿著 lowbit 走，O(log n)
sumRange(l, r) = prefix(r+1) - prefix(l)

Approaches

⭐ Fenwick Tree (BIT) — O(log n) / O(n)

Idea: BIT 維護「部分前綴和」，靠 lowbit 跳躍更新與查詢
Time: update O(log n)、sumRange O(log n)
Space: O(n)

class NumArray(nums: IntArray) {
    private val n = nums.size
    private val tree = IntArray(n + 1)   // 1-indexed BIT
    private val arr = IntArray(n)

    init {
        for (i in nums.indices) update(i, nums[i])
    }

    fun update(index: Int, value: Int) {
        val delta = value - arr[index]
        arr[index] = value
        var i = index + 1
        while (i <= n) {
            tree[i] += delta
            i += i and (-i)       // 跳到下一個負責區段
        }
    }

    fun sumRange(left: Int, right: Int): Int = prefix(right + 1) - prefix(left)

    private fun prefix(i: Int): Int {     // nums[0..i-1] 的和
        var sum = 0
        var idx = i
        while (idx > 0) {
            sum += tree[idx]
            idx -= idx and (-idx)
        }
        return sum
    }
}

Note: Segment Tree Approach

線段樹一樣能做到 update / query 皆 O(log n)，且更通用（可支援區間最大、區間更新等）。BIT 程式碼更短、常數更小，適合「單點更新 + 區間和」這種標準場景；需要更複雜的區間操作時才上線段樹。

🔑 Takeaways

Pattern: 樹狀數組 / 線段樹——在「更新」與「區間查詢」之間取得 O(log n) 平衡
Key trick: i & (-i) 取 lowbit 是 BIT 的靈魂；update 沿 +lowbit 上行、prefix 沿 -lowbit 下行。對照 303（不可變、純前綴和）即可看出何時該升級成 BIT

Intuition

Approaches

🔑 Takeaways

相關題目