树状数组(Binary Indexed Tree或Fenwick Tree)是一种用于高效处理数组前缀和的数据结构,利用二进制特性支持O(log n)时间的单点更新和区间查询操作。
树状数组(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。
树状数组通常使用一个一维数组表示,采用1-indexed(即从索引1开始存储有效数据)的方式:
更新原始数组中索引i的值时,需要更新树状数组中所有包含该索引的节点。
更新步骤:
▼Javascript复制代码function update(i, delta) { i = i + 1; // 转为1-indexed while (i < n) { bit[i] += delta; i += i & -i; } }
查询从1到i的所有元素的和。
查询步骤:
▼Javascript复制代码function query(i) { i = i + 1; // 转为1-indexed let sum = 0; while (i > 0) { sum += bit[i]; i -= i & -i; } return sum; }
树状数组在以下场景中特别有用:
频繁的区间查询和单点更新:如果需要经常计算前缀和并且数组中的值会频繁变化,树状数组是一个很好的选择。
计数应用:如逆序对计数、区间统计等。
2D/多维前缀和:树状数组可以很容易地扩展到多维空间,处理二维甚至多维的前缀和查询。
动态排名统计:通过树状数组可以维护一个动态的排名统计。
通过差分数组技术,树状数组可以支持区间更新,但查询变为单点查询,这样就能在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
树状数组是一种优雅而高效的数据结构,尤其在需要频繁执行前缀和操作和单点更新的场景中,它比简单数组更高效,比线段树更简洁。理解了其背后的二进制原理,可以帮助我们写出更高效的算法。