C ++中的二进制索引树还是Fenwick树？
如果与平面的数字数组进行比较，则Fenwick树在两个操作（元素更新和前缀和计算）之间产生更好的平衡。在m个数字的平面数组的情况下，我们可以存储元素，也可以存储前缀和。在第一种情况下，计算前缀和需要线性时间。在第二种情况下，修改或更新数组元素需要线性时间（在两种情况下，其他操作都可以在恒定时间内完成）。Fenwick树允许两种操作在O（logm）的时间内完成。这是通过将数字表示为树来获得的，其中每个节点的值被视为该子树中数字的总和。树结构允许仅使用O（logm）节点访问来完成操作。
通过考虑基于一个的数组，最容易理解Fenwick树。索引j为2的幂的每个元素都包含前j个元素的总和。其索引指示2的2个（不同）幂的和的元素由从2的前次幂开始的元素之和组成。基本上，每个元素由从树中其父元素开始的值之和组成，并且该父元素为通过清除索引中的最小或最低有效位来找到。
要计算任何给定位置或索引的总和，请考虑位置或索引的二进制扩展，并以二进制形式添加与每个1位相对应的元素。
例如，让我们希望计算前十一个值的总和。二进制中的11是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);
}