树状数组

算法

树状数组(Binary Indexed Tree或Fenwick Tree)是一种用于高效处理数组前缀和的数据结构,利用二进制特性支持O(log n)时间的单点更新和区间查询操作。

算法讲解

树状数组(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]

核心操作

1. 更新操作(update)

更新原始数组中索引i的值时,需要更新树状数组中所有包含该索引的节点。

更新步骤:

  1. 从索引i开始
  2. 不断地加上i & -i,直到超出数组范围
  3. 在每一步都更新对应的树状数组值
▼
Javascript
复制代码
function update(i, delta) { i = i + 1; // 转为1-indexed while (i < n) { bit[i] += delta; i += i & -i; } }

2. 查询前缀和(query)

查询从1到i的所有元素的和。

查询步骤:

  1. 从索引i开始
  2. 不断地减去i & -i,直到i变为0
  3. 在每一步都累加对应的树状数组值
▼
Javascript
复制代码
function query(i) { i = i + 1; // 转为1-indexed let sum = 0; while (i > 0) { sum += bit[i]; i -= i & -i; } return sum; }

时间复杂度

  • 初始化:O(n log n)
  • 单点更新:O(log n)
  • 前缀和查询:O(log n)
  • 区间查询:O(log n)

应用场景

树状数组在以下场景中特别有用:

  1. 频繁的区间查询和单点更新:如果需要经常计算前缀和并且数组中的值会频繁变化,树状数组是一个很好的选择。

  2. 计数应用:如逆序对计数、区间统计等。

  3. 2D/多维前缀和:树状数组可以很容易地扩展到多维空间,处理二维甚至多维的前缀和查询。

  4. 动态排名统计:通过树状数组可以维护一个动态的排名统计。

树状数组的优势

  • 实现简单:相比于线段树,树状数组的代码更加简洁。
  • 常数因子小:在实际应用中,树状数组通常比线段树更快,因为它的常数因子更小。
  • 空间效率高:树状数组只需要与原始数组相同大小的空间。

扩展:区间更新

通过差分数组技术,树状数组可以支持区间更新,但查询变为单点查询,这样就能在O(log n)时间内完成区间更新操作。

使用示例

▼
Javascript
复制代码
// 创建一个树状数组 const bit = new BinaryIndexedTree([0, 2, 1, 4, 3, 6, 5]); // 查询前缀和 console.log(bit.query(2)); // 索引0到2的和: 2+1+4=7 // 更新元素值 bit.update(1, 2); // 将索引1的元素增加2 console.log(bit.query(2)); // 现在索引0到2的和: 2+(1+2)+4=9 // 区间查询 console.log(bit.rangeQuery(1, 3)); // 索引1到3的和: (1+2)+4+3=10

树状数组是一种优雅而高效的数据结构,尤其在需要频繁执行前缀和操作和单点更新的场景中,它比简单数组更高效,比线段树更简洁。理解了其背后的二进制原理,可以帮助我们写出更高效的算法。