Medium

307. Range Sum Query - Mutable

arraydivide-and-conquerdesignbinary-indexed-treesegment-tree

解題說明

Range Sum Query - Mutable

題目描述：實作一個資料結構，支援兩種操作：(1) 將陣列中某個位置的值更新；(2) 查詢某個區間 [left, right] 的元素總和。

解題思路：使用樹狀陣列（Binary Indexed Tree / Fenwick Tree）可以同時高效支援單點更新和區間求和。Fenwick Tree 利用最低有效位（lowbit）的特性，每個節點管理一段特定長度的區間和。更新和查詢的時間複雜度均為 O(log n)。相比線段樹，Fenwick Tree 實作更簡潔且常數因子更小。

C++ 解法

複雜度分析

時間複雜度：建構 O(n log n)，update O(log n)，sumRange O(log n)。

空間複雜度：O(n) — 存儲原始陣列與 Fenwick Tree 各需 O(n)。

虛擬碼

1. Constructor: store original array, build Fenwick tree by adding each element
2. Update(index, val):
   a. Compute diff = val - a[index], update a[index] = val
   b. Propagate diff up the Fenwick tree: for i = index+1; i <= n; i += i & (-i)
3. SumRange(left, right):
   a. Return prefixSum(right+1) - prefixSum(left)
4. PrefixSum(i):
   a. Sum = 0; while i > 0: sum += bit[i], i -= i & (-i)
   b. Return sum

其他解法

線段樹 O(n) 建構：用完整的線段樹支援區間查詢和單點更新。功能更強大（可擴展到區間更新），但實作更複雜且常數因子較大。

分塊（Sqrt Decomposition）：將陣列分成大小約 √n 的塊，每塊維護區間和。更新 O(1)，查詢 O(√n)。實作簡單，適合不需要嚴格 O(log n) 的場景。

延伸思考

如果需要支援區間更新（將 [l, r] 每個元素加上 val），該如何修改？
Fenwick Tree 能否用於求區間最小值？如果不行，為什麼？
若更新操作遠多於查詢操作，哪種資料結構更適合？

Range Sum Query - Mutable — CaffeCode