当前位置：首页 > news >正文

21_动态规划与数据结构结合

news 2025/6/30 3:37:18

菜鸟：老鸟，我最近在处理一个数据操作时遇到了性能问题。我需要计算一个数组中某些子数组的和，但直接计算太慢了，有没有什么更高效的方法？

老鸟：你提到的这个问题其实可以通过动态规划结合数据结构来解决。你听说过动态规划吗？

菜鸟：听说过一些，但不太熟悉。能不能详细讲讲？

老鸟：当然可以。动态规划是一种通过分解问题来减少计算量的技术，它通过记忆化的方式避免重复计算。而当它与合适的数据结构结合时，能大幅提升性能。我们来具体看看吧。

渐进式介绍概念

老鸟：假设你有一个数组 arr，你需要多次查询某个子数组 arr[i:j] 的和。直接计算会很慢，我们可以用动态规划预处理，再用一种数据结构来快速查询。

菜鸟：听起来不错，但具体怎么做呢？

老鸟：我们可以先构建一个数组 prefixSum，其中 prefixSum[i] 表示数组 arr 从起始位置到 i 的和。这样每次查询 arr[i:j] 的和时，可以用 prefixSum[j] - prefixSum[i-1] 来快速计算。

菜鸟：这样确实能减少计算量，但构建 prefixSum 数组需要什么操作呢？

老鸟：好问题。我们来看看代码示例。

代码示例与分析

# 构建prefixSum数组
arr = [1, 2, 3, 4, 5]
prefixSum = [0] * (len(arr) + 1)for i in range(1, len(arr) + 1):prefixSum[i] = prefixSum[i-1] + arr[i-1]# 查询子数组 arr[i:j] 的和
def query_sum(i, j):return prefixSum[j] - prefixSum[i-1]# 示例查询
print(query_sum(2, 4))  # 输出 9

老鸟：在这个代码中，我们首先构建了 prefixSum 数组。构建过程的时间复杂度是 O(n)。然后，每次查询子数组和的时间复杂度是 O(1)。

菜鸟：这样确实比直接计算要快很多。但这个方法在更复杂的场景下也适用吗？

问题与优化

菜鸟：如果我要频繁修改数组中的元素，这个方法还有效吗？每次修改后都要重新构建 prefixSum 数组吗？

老鸟：这是一个好问题。如果数组需要频繁修改，我们可以使用更高级的数据结构，比如线段树或树状数组，它们能在 O(log n) 的时间内更新和查询。

老鸟：我们来看看线段树的例子。

class SegmentTree:def __init__(self, data):self.n = len(data)self.tree = [0] * (2 * self.n)# 构建线段树for i in range(self.n):self.tree[self.n + i] = data[i]for i in range(self.n - 1, 0, -1):self.tree[i] = self.tree[i * 2] + self.tree[i * 2 + 1]def update(self, pos, value):pos += self.nself.tree[pos] = valuewhile pos > 1:pos //= 2self.tree[pos] = self.tree[pos * 2] + self.tree[pos * 2 + 1]def query(self, l, r):l += self.nr += self.nresult = 0while l < r:if l % 2:result += self.tree[l]l += 1if r % 2:r -= 1result += self.tree[r]l //= 2r //= 2return result# 示例使用
data = [1, 2, 3, 4, 5]
seg_tree = SegmentTree(data)
print(seg_tree.query(1, 4))  # 输出 9
seg_tree.update(2, 10)
print(seg_tree.query(1, 4))  # 输出 16