C++ 中的二叉索引树或 Fenwick 树？

与普通的数字数组相比，Fenwick 树在元素更新和前缀和计算这两个操作之间取得了更好的平衡。对于一个包含 m 个数字的普通数组，我们可以存储元素本身，或者存储前缀和。在第一种情况下，计算前缀和需要线性时间；在第二种情况下，修改或更新数组元素需要线性时间（在这两种情况下，另一个操作都可以在常数时间内完成）。Fenwick 树允许这两个操作都在 O(log m) 时间内完成。这是通过将数字表示为树来实现的，其中每个节点的值被视为其子树中数字的总和。这种树结构允许仅使用 O(log m) 次节点访问来完成操作。

通过考虑一个基于 1 的数组，最容易理解 Fenwick 树。每个索引 j 为 2 的幂的元素包含前 j 个元素的总和。索引表示两个（不同）2 的幂之和的元素包含自前一个 2 的幂以来的元素的总和。基本上，每个元素包含自其在树中的父节点以来的值的总和，并且可以通过清除索引中的最小或最低有效位来找到该父节点。

要计算直到任何给定位置或索引的总和，请考虑位置或索引的二进制展开，并添加对应于二进制形式中每个 1 位的元素。

例如，假设要计算前十一个值的总和。十一个是二进制的 1011。这包含三个 1 位，因此必须添加三个元素：1000、1010 和 1011。这些分别包含 1-8、9-10 和 11 的值的总和。

下面是一个简单的 C 实现。

示例

#define LSB(i) ((i) & -(i)) // zeroes all the bits except the minimum or least significant one
int A1[SIZE];
int sum(int i) // Returns the sum from index 1 to i{
   int sum = 0;
   while (i > 0)
   sum += A1[i], i -= LSB(i);
   return sum;
}
void add(int i, int k) // Adds k to element with index i{
   while (i < SIZE)
   A1[i] += k, i += LSB(i);
}

更新于：2020年1月29日

309 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告