307. Range Sum Query - Mutable

解題說明

C++ 解法

複雜度分析

虛擬碼

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

其他解法

延伸思考