307. 区域和检索-数组可修改

题目描述：

给你一个数组 nums ，请你完成两类查询。

其中一类查询要求 更新 数组 nums 下标对应的值

另一类查询要求返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 ，其中 left <= right

实现 NumArray 类：

NumArray(int[] nums) 用整数数组 nums 初始化对象

void update(int index, int val) 将 nums[index] 的值 更新 为 val

int sumRange(int left, int right) 返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 （即，nums[left] + nums[left + 1], …, nums[right]）

测试用例：

示例 1:

输入：
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
输出：
[null, 9, null, 8]
解释：
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // 返回 1 + 3 + 5 = 9
numArray.update(1, 2);   // nums = [1,2,5]
numArray.sumRange(0, 2); // 返回 1 + 2 + 5 = 8

限制及提示：

• 1 <= nums.length <= 3 * 10^4
• -100 <= nums[i] <= 100
• 0 <= index < nums.length
• -100 <= val <= 100
• 0 <= left <= right < nums.length
• 调用 update 和 sumRange 方法次数不大于 3 * 10^4

---

解题分析及思路：

本题可以采用树状数组 🔗进行解答，可以为nums构造一棵二叉索引树tree。

l := len(nums)
tree := make([]int, l+1)
for i := 1; i <= l; i++ {
    index := i
    for index <= l {
        tree[index] += nums[i-1]
        index += lowBit(index)
    }
}

当然离不开两个函数

func lowBit(index int) int {
	return index & -index
}

func sum(index int, a []int) (ans int) {
	for index > 0 {
		ans += a[index]
		index -= lowBit(index)
	}
	return
}

为了保证每次更新能够直到原数组中下标为index的值，除了保存二叉索引树之外，还需要将nums保存下来。

在执行Update函数时，为了后续的求和操作，除了需要更新愿数组时，还需要将tree进行更新。

func (this *NumArray) Update(index int, val int) {
	subVal := val - this.nums[index]
	this.nums[index] = val
	index++
	for index < len(this.tree) {
		this.tree[index] += subVal
		index += lowBit(index)
	}
}

而SumRange函数调用sum方法即可。

func (this *NumArray) SumRange(left int, right int) int {
	return sum(right+1, this.tree) - sum(left, this.tree)
}

复杂度：

• 构造函数：O(nlogn)，其中 nn 是数组 nums 的大小。add 函数的时间复杂度是 O(logn)，总共调用 nn 次。
• update 函数：O(logn)。add 函数的时间复杂度是 O(logn)。
• sumRange 函数：O(logn)。prefixSum 函数的时间复杂度是 O(logn)。

执行结果：

• 执行用时： 460 ms, 在所有 Go 提交中击败了84.96%的用户
• 内存消耗：22.8 MB, 在所有 Go 提交中击败了32.93%的用户