1. 问题描述：
给你一个数组 nums ，请你完成两类查询，其中一类查询要求更新数组下标对应的值，另一类查询要求返回数组中某个范围内元素的总和。
实现 NumArray 类：
NumArray(int[] nums) 用整数数组 nums 初始化对象
void update(int index，int val) 将 nums[index] 的值更新为 val
int sumRange(int left，int right) 返回子数组 nums[left, right] 的总和（即，nums[left] + nums[left + 1]， ...， nums[right]）
示例：
输入：
["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); // 返回 9 ，sum([1,3,5]) = 9
numArray.update(1, 2); // nums = [1,2,5]
numArray.sumRange(0, 2); // 返回 8 ，sum([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
最多调用 3 * 10 ^ 4 次 update 和 sumRange 方法
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/range-sum-query-mutable/
2. 思路分析：
分析题目可以知道我们需要将区间中的某个位置的值更新为某一个值val，并且需要查询数组中某个范围的和，因为涉及到数组的单点更新以及求解某个区间和（前缀和）所以我们可以想到树状数组来解决（这里不能够使用前缀和数组因为需要频繁更新，使用前缀和数组的话每一次更新之后都需要计算前缀和数组所以会导致时间复杂度很高），树状数组往往能够使用到两种情况：一种是单点修改，一种是查询区间和。由题目可知这道题目属于树状数组的裸题，我们只需要结合树状数组的基本步骤解决即可。首先我们需要声明一个树状数组tr来记录对应位置的值（主要使用lowbit函数计算对应位置的值），数组的下标一般从1开始比较方便。树状数组一般涉及到三个方法，lowbit(x)：求解x中对应的二进制位中最低位的1对应的数字，例如x = 4 那么对应的二进制位中最低位的1对应的数字为100，add(x，val)：x位置加上val，query(x)查询[0:x]范围的前缀和。其实我们在使用树状数组解题的时候记住三个函数对应的模板即可，并且初始化树状数组的时候一般将原始的nums数组值插入到树状数组中，也即使用add方法更新树状数组对应位置的值，这三个方法都结合了lowbit函数进行操作。
3. 代码如下：
from typing import List
class NumArray:
# 求解x对应的二进制位中最低位的1对应的数字
def lowbit(self, x: int):
return x & -x
# 往x的位置上加上v, 此时需要更新树状数组对应位置的值
def add(self, x: int, v: int):
n = self.n
tr = self.tr
i = x
while i <= n:
tr[i] += v
i += self.lowbit(i)
# 求解[0:x]的前缀和
def query(self, x: int):
tr = self.tr
i = x
res = 0
while i > 0:
res += tr[i]
i -= self.lowbit(i)
return res
def __init__(self, nums: List[int]):
n = len(nums)
self.n = n
tr = [0] * (n + 1)
self.tr = tr
self.nums = nums
# 初始化树状数组一般的做法是将下面的nums数组值插入到树状数组中, 但是很多情况是结合题目在遍历的时候更新树状数组的值
for i in range(1, n + 1):
self.add(i, nums[i - 1])
# 单点更新: 将i位置的数字更新为val
def update(self, i: int, val: int) -> None:
# 其实就是在树状数组对应的位置加上加上 val - self.nums[i]
self.add(i + 1, val - self.nums[i])
# 注意需要更新对应的列表值
self.nums[i] = val
def sumRange(self, left: int, right: int) -> int:
# 因为索引是从1开始的所以需要right + 1
return self.query(right + 1) - self.query(left)