题目描述：
LeetCode 307题 “Range Sum Query – Mutable”（区间和查询 – 可变）要求实现一个数据结构，支持以下两种操作：
- 更新：更新数组中的一个元素的值。
- 查询：查询一个区间内的所有元素的和。
题目链接： Range Sum Query – Mutable
示例：
Given nums = [1, 3, 5]
sumRange(0, 2) -> 9 update(1, 2) sumRange(0, 2) -> 8
解题思路：
为了高效地实现这两种操作，可以使用树状数组（Binary Indexed Tree，BIT）或线段树（Segment Tree）。这两种数据结构都能在O(log n)的时间复杂度内完成更新和查询操作。
方法一：树状数组（Binary Indexed Tree）
树状数组的基本思想：
- 树状数组是一种基于二进制表示的数据结构，用于高效地处理数组的前缀和问题。
- 每个节点存储的是从某个起点到当前节点的区间和。
实现步骤：
- 初始化：构建树状数组。
- 更新操作：更新某个元素的值，并调整树状数组中的相关节点。
- 查询操作：查询某个区间的和，通过计算前缀和的差值来实现。
代码实现：
class NumArray:
def init(self, nums):
self.n = len(nums)
self.tree = [0] * (self.n + 1)
self.nums = nums
for i in range(self.n):
self.update(i, nums[i])
def update(self, i, val):
delta = val - self.nums[i]
self.nums[i] = val
i += 1
while i <= self.n:
self.tree[i] += delta
i += i & -i
def sumRange(self, i, j):
return self._sum(j) - self._sum(i - 1)
def _sum(self, i):
res = 0
i += 1
while i > 0:
res += self.tree[i]
i -= i & -i示例使用
nums = [1, 3, 5] obj = NumArray(nums) print(obj.sumRange(0, 2)) # 输出 9 obj.update(1, 2) print(obj.sumRange(0, 2)) # 输出 8
方法二：线段树（Segment Tree）
线段树的基本思想：
- 线段树是一种二叉树，每个节点表示一个区间的和。
- 每个节点的左右子节点分别表示其区间的左右子区间的和。
实现步骤：
- 构建线段树：递归地构建每个节点，使其表示对应区间的和。
- 更新操作：递归地更新涉及到的节点。
- 查询操作：递归地查询涉及到的区间和。
代码实现：
class SegmentTree:
def init(self, nums):
self.n = len(nums)
self.tree = [0] (4 self.n)
self.build(nums, 0, 0, self.n - 1)
def build(self, nums, v, tl, tr):
if tl == tr:
self.tree[v] = nums[tl]
else:
tm = (tl + tr) // 2
self.build(nums, 2 * v + 1, tl, tm)
self.build(nums, 2 * v + 2, tm + 1, tr)
self.tree[v] = self.tree[2 * v + 1] + self.tree[2 * v + 2]
def update(self, v, tl, tr, pos, new_val):
if tl == tr:
self.tree[v] = new_val
else:
tm = (tl + tr) // 2
if pos <= tm:
self.update(2 * v + 1, tl, tm, pos, new_val)
else:
self.update(2 * v + 2, tm + 1, tr, pos, new_val)
self.tree[v] = self.tree[2 * v + 1] + self.tree[2 * v + 2]
def sumRange(self, v, tl, tr, l, r):
if l > r:
return 0
if l == tl and r == tr:
return self.tree[v]
tm = (tl + tr) // 2
return self.sumRange(2 * v + 1, tl, tm, l, min(r, tm)) + \
self.sumRange(2 * v + 2, tm + 1, tr, max(l, tm + 1), r)class NumArray: def init(self, nums): self.tree = SegmentTree(nums) self.nums = nums
def update(self, i, val):
self.tree.update(0, 0, len(self.nums) - 1, i, val)
self.nums[i] = val
def sumRange(self, i, j):
return self.tree.sumRange(0, 0, len(self.nums) - 1, i, j)示例使用
nums = [1, 3, 5] obj = NumArray(nums) print(obj.sumRange(0, 2)) # 输出 9 obj.update(1, 2) print(obj.sumRange(0, 2)) # 输出 8
总结
- 树状数组适合处理频繁的单点更新和区间查询问题，实现相对简单。
- 线段树功能更强大，可以处理更复杂的区间操作，但实现较为复杂。
根据具体需求选择合适的数据结构，可以有效地解决问题。希望这些详细的解释和代码实现能帮助你理解和解决LeetCode 307题。
发表回复