LeetCode 树状数组简介题解

LeetCode 树状数组简介题解题目描述介绍树状数组Binary Indexed Tree的基本概念和原理。树状数组简介什么是树状数组树状数组Binary Indexed Tree是一种高效地实现动态数组前缀和的数据结构。它可以在 O(log n) 的时间内完成以下操作单点更新前缀和查询基本原理树状数组利用了整数的二进制表示。对于数组中的每个位置 i其树状数组中存储的元素是原数组中从 i-lowbit(i)1 到 i 的元素的和。其中 lowbit(i) i (-i)表示 i 的二进制表示中最低位的 1。应用场景动态数组前缀和区间和查询逆序数统计代码实现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 def range_query(self, l, r): return self.query(r) - self.query(l - 1) # 测试 def test_fenwick_tree(): ft FenwickTree(5) ft.update(1, 1) ft.update(2, 2) ft.update(3, 3) print(ft.query(3)) # 输出6 print(ft.range_query(2, 3)) # 输出5 if __name__ __main__: test_fenwick_tree()总结树状数组是一种高效的数据结构可以在 O(log n) 的时间内完成单点更新和前缀和查询。