LeetCode 树状数组应用题解

LeetCode 树状数组应用题解

题目描述

总结树状数组的各种应用场景。

树状数组的应用场景

1. 动态数组前缀和

• 快速计算数组的前缀和。
• 快速更新数组中某个位置的值。

2. 逆序数统计

• 统计数组中的逆序对数量。
• 利用树状数组存储已经遍历过的元素。

3. 区间和查询

• 快速计算数组某个区间的元素和。
• 支持区间更新。

4. 离散化

• 将大范围数据映射到小范围索引。
• 配合树状数组处理。

5. 动态排名

• 动态维护元素的排名。
• 快速查询第 k 小的元素。

代码实现

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 test_fenwick_tree(): ft = FenwickTree(5) ft.update(1, 1) ft.update(2, 2) print(ft.query(3)) # 输出：3 if __name__ == "__main__": test_fenwick_tree()

总结

树状数组是一种高效的数据结构，可以应用于多种场景，包括前缀和查询、逆序数统计、区间和查询等。