Fenwick树或二进制索引树的简介。
在本教程中，我们将倾向于
- 获取范围总和
- 更新范围
通过使用芬威克树。
Problem Statement: Given an array you need to find the sum of ranges.
我们需要找到范围[0 – 3]的总和。
2 + 3 + 1 + 5 = 11。
使用暴力破解方法的简单方法。即将所有元素从开始索引添加到结束索引。
这将花费线性时间。
还有其他方法可以解决此问题吗？
是的，采用另一个数组，您可以在其中存储先前索引元素的总和。
例如：
但是这里有一个问题。如果您更新索引2的值以将其添加“ 1”怎么办？
然后您需要在索引2之后的所有元素中添加“ 1”
但是，如果您在索引“ 0”处进行更新，则将花费O（n）时间来更新所有值。
还有其他有效的解决方法吗？
是的，我们可以使用分域树。
Fenwick树基于所有数字都可以由2 ^ n表示的事实。因此，算法将利用此优势使查询速度更快。
我们将借助一个例子来理解Fenwick树。
Fenwick树将对2个操作有用。这些操作我们也将在本章中看到。
- 给定范围时计算总和
- 在给定索引的元素上添加值
考虑具有14个元素的数组，如下所示：
-
给定范围时计算总和
例如，我们需要找到sum（13）。
如上所述，任何数字都可以用2的幂表示。
13可以写成2 ^ 3 + 2 ^ 2 + 2 ^ 0
13 =范围[1,8] +范围[9，12] +范围[13,13]
= 40 + 22 + 1
= 63
因此，我们要做的是预先计算这些范围。因此，当我们获得一个范围来计算总和时，我们首先需要添加这些预先计算的值。
如何预先计算值？
我们计算2的幂的范围。
因此范围将是1、2、4、8、16、32…
在第一层的示例中，可以如下计算
如上图所示，我们可以推断出以下3点：
- 我们正在基于2的幂计算范围。
- 在计算范围值时，存在差距
- 我们停在2 ^ 3。因为2 ^ 4是16，所以不在我们数组的范围内。
因此，我们计算了级别0。下一个是级别1，我们从间隙开始计算了同样的级别。
在此之前，让我们标记我们计算出的值的索引。
在填补空白的同时，我们需要考虑连续的空白。
从图像中，索引[3，3]仅具有1个间隙。因此，我们计算2 ^ 0 = 1。
间隙再次从索引[5]开始，它具有连续的3个间隙。因此我们计算2 ^ 0，2 ^ 1。我们不需要计算2 ^ 2，因为它的长度是4，并且我们的间隔也没有那么长。因此，我们把它留在那里。
现在我们看一下索引[7，7]，因为它只有1个间隙，所以我们仅计算2 ^ 0。
下一个间隔是从索引9到14。在这里，我们再次计算从2 ^ 0开始的值。
现在，我们再次从索引11开始。由于只有1个间隙，因此我们按原样编写。
下一个索引是13，间隔是2。因此，我们求和范围是2 ^ 0，2 ^ 1。它可以显示如下：
现在我们已经覆盖了所有索引，我们可以执行求和范围查询。
现在我们想知道范围13的总和。我们可以写成
总和（13）=范围[1，8] +范围[9，12] +范围[13，13] /
现在，我们可以轻松计算出如下图所示：
我们只需要添加突出显示的值，便得到结果“ 63”。
现在，这实际上对我们有什么帮助？让我为您简化。
下图以二进制数表示索引
现在范围的索引是：
1000 + 1100 + 1101
如果您观察到二进制的13的索引是“ 1101”。当您将最后一个数字“ 1”翻转为“ 0”时，您将获得下一个要添加的索引，即“ 1100”。现在再次将最后一个“ 1”翻转为“ 0”，您将得到下一个要添加的索引“ 1000”。
如何删除最后设置的位：
通过执行x获得最后设置的位& (-x)
然后通过x –x（x&(-x))
在我们的示例中：
X = 13 = 00001101
-X = -13 = 11110011
X & -X = 00000001
X –（X& (-X)) = 00001100
现在我们在给定的索引处添加一个元素。
假设我们给索引5加2。
从索引5开始加2。如果不使用Fenwick树，则需要从索引5开始向所有范围加2。
但是，当我们构造了芬威克树时，我们将看到如何做。
对于索引5，首先将2添加到索引5的元素
然后，我们将更新索引5右侧的所有范围。由于只有一个范围[5，6]，我们将对其进行更新。
在索引6之后，没有与5相关的连续范围。因此，我们上一层并更新所有范围。
现在我们转到索引8并用2更新值。
因此，我们完成了更新值。
现在，让我们看看如何通过二进制表示来实现这一点：
首先，我们转到“ 5”，即0101，然后转到0110，从那里转到1000。
基本上，我们添加最后一个设置位以了解下一个要更新的索引。
通过编程可以实现以下目的：
通过执行x获得最后设置的位& (-x)
然后将最后一个设置位加x + x（x&(-x))
Fenwick树在C中的实现
#include <stdio.h>
int FWtree[100] = {0};
int SIZE;
int get_sum(int i)
{
int sum = FWtree[i];
while(i)
{
i -= (i & (-i));
sum += FWtree[i];
}
return sum;
}
void add(int i, int value)
{
while(i < SIZE)
{
FWtree[i] += value;
i += (i & (-i));
}
}
void init_fw_tree(int my_array[], int start, int end)
{
SIZE = end-start+2;
for(int i = 1; i <= end-start+2; i++)
{
add(i, my_array[ start+i-1 ]);
}
}
int main()
{
int my_array[] = {1, 3, 2, 4, 5 ,8, 6, 5 ,0, 3, 4, 3, 2, 2};
init_fw_tree(my_array, 0, 13);
//get sum of all the numbers in the array
printf("The sum of all the numbers in the array is = %d\n",get_sum(14));
// update 5th index with value 8
add(5,8);
printf("The new sum after updating 5th index with value 8 is = %d\n",get_sum(14));
return 0;
}
输出：
The sum of all the numbers in the array is = 48 The new sum after updating 5th index with value 8 is = 56
进一步阅读：
AJ关于DS和算法的权威指南。单击此处以学习算法和数据结构教程的完整列表。 85多个章节可供学习。
该网站上可用的教程列表：
| C编程20+章 | C ++编程80+章 |
| 100多个编码问题 | 数据结构和算法85+章 |
| 系统设计20+章 | Shell脚本编写12章 |
| 4g LTE 60+章节 | 最常见的编码问题 |
| 5G NR 50+章 | Linux系统编程20+章 |
