LeetCode 区域和检索题解

LeetCode 区域和检索题解题目描述给定一个整数数组实现一个数据结构支持以下操作更新更新数组中某个位置的值检索返回数组中某个区间的元素和示例NumArray nums new NumArray([1, 3, 5]); nums.sumRange(0, 2); // 返回 9 nums.update(1, 2); // 更新数组 nums.sumRange(0, 2); // 返回 8解题思路方法树状数组思路使用树状数组存储数组的前缀和。更新时修改树状数组中对应的位置。查询时使用前缀和相减。复杂度分析时间复杂度O(log n)。空间复杂度O(n)。代码实现class FenwickTree: def __init__(self, n): self.n n self.tree [0] * (n 1) def update(self, i, delta): while i self.n: self.tree[i] delta i i (-i) def query(self, i): result 0 while i 0: result self.tree[i] i - i (-i) return result class NumArray: def __init__(self, nums): self.n len(nums) self.tree FenwickTree(self.n) self.nums nums for i in range(self.n): self.tree.update(i 1, nums[i]) def update(self, index, val): delta val - self.nums[index] self.nums[index] val self.tree.update(index 1, delta) def sum_range(self, left, right): return self.tree.query(right 1) - self.tree.query(left) # 测试 def test_num_array(): nums NumArray([1, 3, 5]) print(nums.sum_range(0, 2)) # 输出9 nums.update(1, 2) print(nums.sum_range(0, 2)) # 输出8 if __name__ __main__: test_num_array()总结树状数组可以高效地实现区域和检索支持 O(log n) 的更新和查询操作。