LeetCode 区间增加单点查询题解

LeetCode 区间增加单点查询题解题目描述给定一个整数数组实现以下操作增加给某个区间的所有元素增加一个值查询返回数组中某个位置的值解题思路方法树状数组差分思路使用差分数组和树状数组。区间增加时在差分数组的两端进行修改。单点查询时计算差分数组的前缀和。复杂度分析时间复杂度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 RangeUpdate: def __init__(self, nums): self.n len(nums) self.diff [0] * (self.n 1) for i in range(self.n): self.range_update(i 1, i 1, nums[i]) def range_update(self, l, r, val): self._add(l, val) self._add(r 1, -val) def _add(self, i, val): while i self.n: self.diff[i] val i i (-i) def point_query(self, i): result 0 while i 0: result self.diff[i] i - i (-i) return result # 测试 def test_range_update(): ru RangeUpdate([1, 2, 3]) print(ru.point_query(1)) # 输出1 ru.range_update(1, 2, 1) print(ru.point_query(2)) # 输出3 if __name__ __main__: test_range_update()总结树状数组可以高效地实现区间增加和单点查询操作。