当前位置：首页 > news >正文

二叉树算法之 Fenwick 树（Binary Indexed Tree, BIT）详细解读

news 2024/10/22 9:43:58

Fenwick 树，也称为 树状数组 或 二进制索引树（Binary Indexed Tree, BIT），是一种用于处理动态数组前缀和查询和修改的数据结构。它提供了一种高效的方法来在动态数据中求解区间和问题，并支持单点更新和区间查询操作。

Fenwick 树的优势在于它能够以 O(log n) 的时间复杂度进行区间查询和更新操作，适用于场景包括动态维护数组前缀和、逆序对计算等问题。

1. Fenwick 树的基本概念

Fenwick 树维护一个数组，通过二进制的方式对前缀和进行分块存储。其核心思想是利用数组的下标和二进制表示的性质，将数组划分为若干区间，每个区间的大小为2的某个次方。

Fenwick 树的基本操作：

单点更新：将数组的某个元素增加一个值。
前缀和查询：求数组从起点到某个位置的区间和。

通过这些操作，可以高效地处理数据的动态更新和快速查询。

2. Fenwick 树的存储结构

Fenwick 树使用一个数组 BIT[] 来存储数据，每个位置 i 存储的是一个子数组的和。对于每个下标 i，可以通过最低位为1的二进制位来确定该位置所代表的区间长度。例如：

BIT[4] 代表数组中第1至第4个元素的和。
BIT[6] 代表数组中第5和第6个元素的和。

3. 基本操作的实现

Fenwick 树支持两种基本操作：

更新操作：将某个位置的元素增加一个值。
查询操作：求解前缀和，即从数组的起始位置到某个位置的区间和。

3.1 单点更新操作（Update）

更新操作的目标是将数组中的某个元素增加一个值，同时保持 Fenwick 树中相关的前缀和信息一致。

更新的具体过程是，从修改的那个元素开始，逐步将对应的树状数组中的父节点值更新。父节点的下标通过将当前下标的最低位为1的二进制位加到当前下标上来确定。

// 在 index 位置增加 delta 值
void update(int index, int delta, int[] BIT, int n) {while (index <= n) {BIT[index] += delta;index += index & -index;  // 移动到下一个需要更新的父节点}
}

在 update 操作中，index += index & -index 是通过获取下标 index 的最低有效位（Lowest Significant Bit, LSB）来确定下一个要更新的父节点的位置。

3.2 前缀和查询操作（Query）

查询操作的目标是求解从数组的起始位置到某个位置的区间和。Fenwick 树存储的是部分前缀和，因此可以通过逐步累加相关节点的值来计算结果。

// 查询从 1 到 index 的前缀和
int query(int index, int[] BIT) {int sum = 0;while (index > 0) {sum += BIT[index];index -= index & -index;  // 移动到下一个需要累加的父节点}return sum;
}

在 query 操作中，index -= index & -index 是通过获取下标 index 的最低有效位来确定下一个要查询的父节点。

4. Fenwick 树的实现

以下是一个 Fenwick 树的 Java 实现，包括对数组进行单点更新和前缀和查询的功能：

class FenwickTree {private int[] BIT;  // 树状数组private int n;      // 数组大小// 构造函数，初始化树状数组public FenwickTree(int size) {n = size;BIT = new int[n + 1];  // BIT[0] 不使用，因此数组长度为 n+1}// 单点更新操作：在 index 位置增加 deltapublic void update(int index, int delta) {while (index <= n) {BIT[index] += delta;index += index & -index;  // 移动到下一个需要更新的父节点}}// 查询操作：获取从 1 到 index 的前缀和public int query(int index) {int sum = 0;while (index > 0) {sum += BIT[index];index -= index & -index;  // 移动到下一个需要累加的父节点}return sum;}// 查询操作：获取区间 [l, r] 的和public int queryRange(int l, int r) {return query(r) - query(l - 1);}
}public class Main {public static void main(String[] args) {// 创建大小为10的树状数组FenwickTree fenwickTree = new FenwickTree(10);// 在位置3增加5fenwickTree.update(3, 5);// 查询前缀和（从位置1到5的和）System.out.println("前缀和1到5: " + fenwickTree.query(5)); // 输出: 5// 在位置6增加10fenwickTree.update(6, 10);// 查询区间和（从位置3到6的和）System.out.println("区间和3到6: " + fenwickTree.queryRange(3, 6)); // 输出: 15}
}