教程目录

想要实际看看算法是如何工作的吗?

通过交互式可视化深入理解算法运行过程

查看算法可视化

树状数组(Binary Indexed Tree)数据结构

树状数组(Binary Indexed Tree),也称为Fenwick Tree,是一种支持高效的前缀和计算和单点更新的数据结构。它的核心思想是利用二进制的性质来维护数据间的层级关系,从而在O(log n)的时间内完成查询和更新操作。

基本原理

树状数组的关键概念是"父子关系",这种关系是通过二进制表示中的最低位1来确定的。对于任意一个节点i,它的父节点是i + (i & -i),更新操作就是沿着这条路径向上进行的。而i - (i & -i)并不是i的子节点,它是查询前缀和时要访问的下一个节点:它管理的区间紧挨在i所管理区间的左侧。例如i = 6时,6 - 2 = 4,但4的父节点是8而不是6。

  • i & -i 表达式计算的是i的二进制表示中的最低位1对应的值
  • 例如:6的二进制是110,6&(-6) = 6&(010) = 2

存储结构

树状数组通常使用一个一维数组表示,采用1-indexed(即从索引1开始存储有效数据)的方式:

  • BIT[i]存储了原始数组中某个区间的和
  • 每个BIT[i]负责管理的区间长度由i & -i决定
  • 例如,BIT[6]管理的区间长度是2,包含原始数组中的A[5]和A[6]

核心操作

...

目录