LeetCode 树状数组与线段树对比题解题目描述对比树状数组和线段树的优缺点。树状数组 vs 线段树树状数组的优点实现简单代码量少空间复杂度低常数时间小树状数组的缺点功能有限不能高效处理区间修改和区间查询线段树的优点功能强大可以处理区间修改和区间查询适用范围广线段树的缺点实现复杂空间复杂度高常数时间大代码实现# 树状数组 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 SegmentTree: def __init__(self, nums): self.n len(nums) self.tree [0] * (4 * self.n) self.build(1, 0, self.n - 1, nums) def build(self, node, l, r, nums): if l r: self.tree[node] nums[l] else: mid (l r) // 2 self.build(node * 2, l, mid, nums) self.build(node * 2 1, mid 1, r, nums) self.tree[node] self.tree[node * 2] self.tree[node * 2 1] def query(self, node, l, r, ql, qr): if ql r or qr l: return 0 if ql l and r qr: return self.tree[node] mid (l r) // 2 return self.query(node * 2, l, mid, ql, qr) self.query(node * 2 1, mid 1, r, ql, qr) # 测试 def test_comparison(): ft FenwickTree(5) ft.update(1, 1) print(ft.query(3)) # 输出1 st SegmentTree([1, 2, 3, 4, 5]) print(st.query(1, 0, 4, 0, 2)) # 输出6 if __name__ __main__: test_comparison()总结树状数组和线段树各有优缺点应根据具体问题选择合适的数据结构。