提示信息

数据结构编程实践:Python版系列第12讲——树状数组

淡淡浅香 已关注

第12讲:树状数组(Binary Indexed Tree)基础与应用

树状数组,又称为二叉索引树(Fenwick Tree),是一种用于高效处理数组前缀和与修改操作的数据结构。与线段树类似,树状数组的目标是在支持数组更新的同时,实现快速的前缀和查询。树状数组的时间复杂度通常为 O(log n),这在很多应用中具有很高的效率。

1. 树状数组的基本概念

树状数组的核心思想是使用一个辅助数组(称为 BIT 数组)来存储部分和。BIT 数组的每个节点保存了一个范围内的累加和,通过这种方式,我们可以在 O(log n) 的时间内计算出任意前缀和。

2. 树状数组的结构

假设我们有一个长度为 n 的数组 arr,我们定义一个大小为 n+1 的 BIT 数组(通常索引从 1 开始)。BIT 数组中的每个索引 i 都代表了 arr 中某个区间的和,各个区间的大小和位置由二进制表示决定。

3. 树状数组的基本操作

树状数组的两个核心操作是更新和前缀和查询。

更新操作

当 arr 中的一个元素发生变化,我们需要更新 BIT 数组。设更新位置为 idx,增量为 delta,更新操作如下:

  1. def update(bit, n, idx, delta):
  2. while idx <= n:
  3. bit[idx] += delta
  4. idx += idx & -idx # 利用低位来移动节点

前缀和查询

为了得到 arr 中前 i 个元素的和,我们进行如下操作:

  1. def query(bit, idx):
  2. sum_ = 0
  3. while idx > 0:
  4. sum_ += bit[idx]
  5. idx -= idx & -idx # 移动到父节点
  6. return sum_

4. 树状数组的初始化

我们需要初始化 BIT 数组,从而可以使用以上操作。通常初始化 BIT 数组为 0,然后根据 arr 内容进行批量更新。

  1. def build_bit(arr):
  2. n = len(arr)
  3. bit = [0] * (n + 1)
  4. for idx, val in enumerate(arr, start=1):
  5. update(bit, n, idx, val)
  6. return bit

5. 应用案例

树状数组在很多场景中是非常有用的,例如:

  • 动态维护数组的前缀和:在金融、统计等领域,实时更新数据并查询累积值。
  • 逆序数计算:在一定范围内,统计有多少数对满足某种关系。

6. 示例代码

以下是完整的代码示例,展示了树状数组的创建、更新和查询操作:

  1. class FenwickTree:
  2. def __init__(self, size):
  3. self.size = size
  4. self.bit = [0] * (size + 1)
  5. def update(self, idx, delta):
  6. while idx <= self.size:
  7. self.bit[idx] += delta
  8. idx += idx & -idx
  9. def query(self, idx):
  10. sum_ = 0
  11. while idx > 0:
  12. sum_ += self.bit[idx]
  13. idx -= idx & -idx
  14. return sum_
  15. def build(self, arr):
  16. for idx, val in enumerate(arr, start=1):
  17. self.update(idx, val)
  18. # 应用示例
  19. arr = [1, 2, 3, 4, 5]
  20. fenwick_tree = FenwickTree(len(arr))
  21. fenwick_tree.build(arr)
  22. # 查询前缀和
  23. print(fenwick_tree.query(3)) # 输出 6 (arr[0] + arr[1] + arr[2])
  24. # 更新
  25. fenwick_tree.update(3, 2) # arr[2] = 3 + 2
  26. print(fenwick_tree.query(3)) # 输出 8 (1 + 2 + 5)

通过这一讲,你应该对树状数组有了初步了解。随着练习与应用,你将能更好地掌握这一高效的数据结构。

    遇到难题? "AI大模型GPT4.0、GPT" 是你的私人解答专家! 点击按钮去提问......
淡淡浅香 关注 已关注

最近一次登录:2024-11-21 01:22:22   

暂时还没有签名,请关注我或评论我的文章
×
免费图表工具,画流程图、架构图