Java 中的 Fenwick 树

在本节中，我们将学习 Java 中的 Fenwick 树。Fenwick 树也称为二叉索引树（BIT）。

使用 Fenwick 树的场景

让我们了解一下在何种场景下会用到线段树。

假设我们有一个数组 a[] = {0, 1, …, s - 1}，并希望对给定数组执行以下两个任务：

• 计算数组元素从索引 m 到 n 的和，其中 0 <= m <= n <= s - 1
• 更改数组 a[] 中某个元素的值为其新值 nv，即需要执行 a[j] = nv，其中 0 <= j <= s - 1。

为了找到上述两个任务的解决方案，我们可以使用线段树或 Fenwick 树。线段树提供优化的解决方案。与线段树类似，Fenwick 树也可以使用数组表示。Fenwick 树的好处是易于编码，并且比线段树占用的空间更少。

注意：建议先阅读 Java 中的线段树主题，以便更好地理解 Fenwick 树。

使用数组表示 Fenwick 树

如上所述，Fenwick 树使用数组表示。令 fenArr[] 数组表示 Fenwick 树。Fenwick 树中的每一个节点都包含输入数组中某些元素的和。Fenwick 树的大小与输入数组的大小（在本例中为 s）相同。

使用数组构建 Fenwick 树

首先，我们为 fenArr[] 数组分配内存，然后将该数组初始化为 0。之后，我们就可以在该数组上执行各种操作。

Fenwick 树上的操作

计算给定输入数组 a[] 的子数组的和：要计算子数组元素的和，我们实现 getArrSum(y) 方法。

getArrSum(y)：使用由输入数组 a[0, …, n] 构建的 fenArr[] 返回子数组 ar[0, …, y] 的和。

步骤 1：将结果总和初始化为 0，当前索引初始化为 y + 1。

步骤 2：重复步骤 a 和 b，直到当前索引大于 0。

1. 将 fenArr[idx] 添加到总和中。
2. 转到 fenTree[idx] 的父节点。父节点可以通过截断当前索引的最后一位设置位来找到，即 idx = idx - (idx & (-idx))

步骤 3：返回总和。

更新特定索引处的值：要实现特定索引处的更新，我们实现 **updateFenwick()** 方法。请注意，更新特定索引处的值不会对输入数组 a[] 产生任何影响。它只会对 fenArr[] 数组产生影响。

updateFenwick(y, v)：该方法将索引 y 处的值更新为值 u。

步骤 1：将 y + 1 赋值给当前索引。

步骤 2：重复步骤 a 和 b，直到当前索引等于或小于 s。

1. 将值 v 添加到 fenArr[idx] 中。
2. 转到 fenArr[idx] 的下一个元素。通过设置当前索引的最后一位设置位可以找到下一个元素，即 idx = idx + (idx & (-idx))。

Fenwick 树的工作原理

我们知道任何正数都可以表示为 2 的幂之和，这个思想已被用于 Fenwick 树。例如，21 可以写成 2⁴ + 2² + 2⁰ = 16 + 4 + 1。Fenwick 树的每个节点都包含 p 个元素的和，其中 p 是 2 的幂。考虑上面的图（getArrSum() 操作的图），前 12 个元素的总和可以通过将最后 4 个元素（从 9 到 12）相加，再加上前 8 个元素（从 1 到 8）的总和来实现。在二进制表示中，数字 n 的设置位数最多为 O(log(n))。因此，在 getArrSum() 和 updateFenwick() 操作中，都需要遍历最多 O(log(n)) 个节点。因此，由于对所有 n 个元素都调用了 updateFenwick() 操作，构建的时间复杂度为 O(n * log(n))。

Fenwick 树的实现

让我们来实现 Fenwick 树以及上面定义的操作。

文件名： FenwickTreeExample.java

输出

Sum of the elements in array a[0 ... 6] is: 161
Sum of the elements in array a[0 ... 6] after update is: 168