数据结构编程实践: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,更新操作如下:
def update(bit, n, idx, delta):
while idx <= n:
bit[idx] += delta
idx += idx & -idx # 利用低位来移动节点
前缀和查询
为了得到 arr 中前 i 个元素的和,我们进行如下操作:
def query(bit, idx):
sum_ = 0
while idx > 0:
sum_ += bit[idx]
idx -= idx & -idx # 移动到父节点
return sum_
4. 树状数组的初始化
我们需要初始化 BIT 数组,从而可以使用以上操作。通常初始化 BIT 数组为 0,然后根据 arr 内容进行批量更新。
def build_bit(arr):
n = len(arr)
bit = [0] * (n + 1)
for idx, val in enumerate(arr, start=1):
update(bit, n, idx, val)
return bit
5. 应用案例
树状数组在很多场景中是非常有用的,例如:
- 动态维护数组的前缀和:在金融、统计等领域,实时更新数据并查询累积值。
- 逆序数计算:在一定范围内,统计有多少数对满足某种关系。
6. 示例代码
以下是完整的代码示例,展示了树状数组的创建、更新和查询操作:
class FenwickTree:
def __init__(self, size):
self.size = size
self.bit = [0] * (size + 1)
def update(self, idx, delta):
while idx <= self.size:
self.bit[idx] += delta
idx += idx & -idx
def query(self, idx):
sum_ = 0
while idx > 0:
sum_ += self.bit[idx]
idx -= idx & -idx
return sum_
def build(self, arr):
for idx, val in enumerate(arr, start=1):
self.update(idx, val)
# 应用示例
arr = [1, 2, 3, 4, 5]
fenwick_tree = FenwickTree(len(arr))
fenwick_tree.build(arr)
# 查询前缀和
print(fenwick_tree.query(3)) # 输出 6 (arr[0] + arr[1] + arr[2])
# 更新
fenwick_tree.update(3, 2) # arr[2] = 3 + 2
print(fenwick_tree.query(3)) # 输出 8 (1 + 2 + 5)
通过这一讲,你应该对树状数组有了初步了解。随着练习与应用,你将能更好地掌握这一高效的数据结构。