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 能否用於求區間最小值?如果不行,為什麼?
- 若更新操作遠多於查詢操作,哪種資料結構更適合?