Fenwick Range Sum (Binary Indexed Tree)

Design a data structure that supports:

• updating an index in an array
• querying the sum of a range [left, right]

Implement a NumArray using a Fenwick Tree (Binary Indexed Tree).

Function signature

type NumArray struct { /* ... */ }

func Constructor(nums []int) NumArray
func (n *NumArray) Update(index int, val int)
func (n *NumArray) SumRange(left int, right int) int

Examples

Example 1:

Input:
nums = [1,3,5]
SumRange(0,2) -> 9
Update(1,2)
SumRange(0,2) -> 8

Example 2:

Input:
nums = [0,0,0]
Update(0,5)
SumRange(0,1) -> 5

Constraints

• 1 <= nums.length <= 10^5
• -10^5 <= nums[i], val <= 10^5
• 0 <= index < nums.length

Hints

1. Fenwick Tree supports prefix sums in O(log n).
2. Range sum = prefix(right) - prefix(left-1).
3. Store the current array to compute delta on update.

Notes

• This is a classic alternative to segment trees for sums.
• The tree is 1-indexed internally.