二进制索引（Fenwick）树

1. Introduction

二进制索引（Fenwick）树是一种数据结构，为实现动态累积频率表提供了高效的方法。

这种Fenwick树数据结构使用了许多位操作技术。在这个可视化中，我们将使用Fenwick树这个术语来指代这种数据结构（通常缩写为'FT'），因为二进制索引树的缩写'BIT'通常与常见的位操作相关联。

1-1. 累积频率表

假设我们有一个整数的多重集s = {2,4,5,6,5,6,8,6,7,9,7}（不一定排序）。s中有n = 11个元素。假设我们将要使用的最大整数是m = 10，我们从不使用整数0。例如，这些整数代表学生（整数）的分数范围在[1..10]。注意n与m无关。

我们可以通过一个简单的O(n)时间循环（回忆计数排序的第一次计数过程）从s创建一个频率表f。然后我们可以使用类似于DP 1D前缀和的技术在O(m)时间内从频率表f创建累积频率表cf，例如，在下表中，cf[5] = cf[4]+f[5] = 2+2 = 4，然后cf[6] = cf[5]+f[6] = 4+3 = 7。

1-2. 范围和查询：rsq(i, j)

有了这样的累积频率表cf，我们可以执行范围求和查询：rsq(i, j)，以返回索引i和j（包含）之间的频率之和，以高效的O(1)时间，再次使用DP 1D前缀和（即，包含-排除原则）。例如，rsq(5, 9) = rsq(1, 9) - rsq(1, 4) = 11-2 = 9。由于这些键：5、6、7、8和9代表分数，rsq(5, 9)意味着在5到9之间得分的学生总数（9）。

1-3. 动态累积频率表

动态数据结构需要在查询之间支持（频繁的）更新。例如，我们可能会更新（增加）分数7的频率从2 → 5（例如，又有3个学生得分7）并更新（减少）分数9的频率从1 → 0（例如，之前得分9的1个学生被发现抄袭作业，现在被罚为0，即，从分数中移除），从而更新表格为：

用纯数组基础数据结构来实现这个动态累积频率表将需要O(m)的更新操作。我们能做得更好吗？

2. 模式和第一/默认模式

介绍：Fenwick 树数据结构。

在这个可视化中，Fenwick 树有三种使用模式。

第一种模式是默认的 Fenwick 树，它可以在 O(log n) 中处理点更新 (PU)和范围查询 (RQ)，其中 n 是数据结构中最大的（整数）索引/键。请记住，数据结构中实际的键数由另一个变量 m 表示。我们将这种默认类型简称为 PU RQ，即点更新范围查询。

这种巧妙的整数键排列思想最初出现在Peter M. Fenwick 的 1994 年论文中。

3. 点更新范围查询 (PU RQ)

您可以点击'创建'菜单来创建一个频率数组f，其中f[i]表示键i在我们原始键数组s中出现的频率。

重要提示：这个频率数组f不是原始键数组s。例如，如果您输入{0,1,0,1,2,3,2,1,1,0}，这意味着您正在创建0个一，1个二，0个三，1个四，2个五，...，0个十（基于1的索引）。在这个例子中，最大的索引/整数键是m = 10，就像在之前的幻灯片中一样。

如果您有原始数组s，包含n个元素，例如，从之前的幻灯片中的{2,4,5,6,5,6,8,6,7,9,7}（s不需要排序），您可以进行一次O(n)的遍历，将s转换为n个索引/整数键的频率表f。（我们将在不久的将来提供这种替代输入方法）。

您可以点击'随机化'按钮来生成n个键[1..n]的随机频率。

点击'开始'来迭代调用n次update(i, f[i])操作。（我们将在不久的将来提供一个更快的构建FT功能）。

3-1. 可视化 - 第一部分

尽管从概念上讲，这个数据结构是一个树，但它将被实现为一个名为ft的整数数组，范围从索引1到索引n（我们牺牲了我们的ft数组的索引0）。上面显示的Fenwick树的（黑色轮廓和白色内部）顶点中的值是存储在基于1的Fenwick树ft数组中的值。

目前，这个Fenwick树的边还没有显示出来。树有两个版本，查询树和更新树。

3-2. 可视化 - 第二部分

底部（蓝色内部）顶点内的值是频率数组 f 的值。

3-3. 可视化 - 第三部分

在数组ft中索引i存储的值（Fenwick树中的顶点i），即ft[i]，是键范围[i-LSOne(i)+1 .. i]的累积频率。在视觉上，这个范围由Fenwick树（查询/查询版本）的边缘显示。

关于LSOne(i) = (i) & -(i)操作的复习，请参见我们的位掩码可视化页面。

3-4. 例子： ft[4] = rsq(1, 4)

ft[4] = 2 存储了键在 [4-LSOne(4)+1 .. 4] 中的累积频率。
(沿着从索引4向上回到索引0的边缘，再加上1个索引)。
这是 [4-4+1 .. 4] = [1 .. 4] 和 f[1]+f[2]+f[3]+f[4] = 0+1+0+1 = 2。

3-5. 例子：ft[6] = rsq(5, 6)

ft[6] = 5 存储了键在 [6-LSOne(6)+1 .. 6] 中的累积频率。
(沿着从索引6向上回到索引4的边，再加1个索引)。
这是 [6-2+1 .. 6] = [5 .. 6] 和 f[5]+f[6] = 2+3 = 5。

3-6. 范围查询：rsq(j)

函数 rsq(j) 返回从第一个索引 1（忽略索引 0）到索引 j 的累积频率。

这个值是存储在数组 ft 中与 j 相关的子频率之和，关系公式为 j' = j-LSOne(j)。这种关系形成了一个Fenwick树，具体来说，是Fenwick树的'询问树'。

我们将这个公式反复应用，直到 j 为0。

无论 n 的值如何，这个函数的运行时间都是 O(log m)。讨论：为什么？

3-7. Example: rsq(6) = ft[6]+ft[4]

我们之前已经看到 ft[6] = rsq(5, 6) 和 ft[4] = rsq(1, 4)。
因此，rsq(6) = ft[6] + ft[6-LSOne(6)] = ft[6] + ft[6-2] =
ft[6] + ft[4] = 5 + 2 = 7。
附注：4-LSOne(4) = 4-4 = 0。

3-8. 范围查询：rsq(i, j)

rsq(i, j) 返回从索引 i 到 j（包含）的累积频率。

如果 i = 1，我们可以像之前那样使用 rsq(j)。
如果 i > 1，我们只需要返回：rsq(j) – rsq(i–1)（包容-排斥原理）。

讨论：你理解原因吗？

这个函数也在 O(log m) 中运行，无论 n 如何。讨论：为什么？

3-9. 例子： rsq(4, 6) = rsq(6) - ...

rsq(4, 6) = rsq(6) – [下一张幻灯片...]。
我们之前已经看到rsq(6) = ft[6]+ft[4] = 5+2 = 7。

3-10. 例子：rsq(4, 6) = rsq(6) - rsq(3)

rsq(4, 6) = rsq(6) – rsq(3)。
我们可以类似地计算出rsq(3) = ft[3]+ft[2] = 0+1 = 1。

3-11. 例子：rsq(4, 6) = 7 - 1 = 6

3-12. 点更新：update(i, v)

要更新键（索引）i的频率为v（v可以是正数或负数；|v|不一定为一），我们使用update(i, v)。

与i相关的索引通过i' = i+LSOne(i)与v相关，当i < ft.size()时（注意ft.size()是m+1（我们忽略了索引0）。这些关系形成了一种叫做'更新树'的Fenwick树结构的变体。

讨论：你理解这个操作以及我们为什么避免索引0吗？

这个函数也以O(log m)运行，无论n如何。讨论：为什么？

4.

第二模式

Fenwick 树的第二种模式是可以处理范围更新 (RU)，但只能以 O(log n) 处理点查询 (PQ)。

我们将此类型缩写为RU PQ。

5. 范围更新点查询 (RU PQ)

创建数据并尝试在其上运行范围更新或点查询算法。为此类型创建数据意味着插入几个区间。例如，如果您输入[2,4],[3,5]，这意味着我们正在通过+1更新范围2到4，然后通过+1更新范围3到5，因此我们有以下频率表：0,1,2,2,1，这意味着有1个0，2个1，3个2，4个2，5个1。

5-1. RU PQ 可视化

顶部的顶点显示了存储在Fenwick树中的值（ft数组）。

底部的顶点显示了数据的值（频率表f）。

注意到这种RU PQ类型中使用的Fenwick树的巧妙修改：我们将范围的开始增加+1，但将范围结束后的一个索引减少-1以达到这个结果。

6.

我们正在探索模式中。

Fenwick 树的第三种模式是可以同时处理范围更新 (RU)和范围查询 (RQ)的模式，其时间复杂度为 O(log n)，使得这种类型与具有懒惰更新的线段树相当，后者也可以在 O(log n) 的时间复杂度内进行 RU RQ。

7. 范围更新范围查询 (RU RQ)

创建数据并尝试在其上运行范围更新或范围查询算法。

创建数据是插入几个间隔，类似于 RU PQ 版本。但是这次，你也可以高效地进行范围查询。

7-1. RU RQ 可视化

在范围更新范围查询 Fenwick 树中，我们需要有两个 Fenwick 树。顶部的顶点显示第一个 Fenwick 树的值（BIT1[] 数组），中间的顶点显示第二个 Fenwick 树的值（BIT2[] 数组），而底部的顶点显示数据的值（频率表）。第一个 Fenwick 树的行为与 RU PQ 版本相同。第二个 Fenwick 树用于进行巧妙的偏移，以再次允许范围查询。

8. 额外

我们有一些涉及此数据结构的额外内容。

8-1. 实施

遗憾的是，截至2020年，这种数据结构在C++ STL、Java API、Python或OCaml标准库中尚未提供。因此，我们必须编写我们自己的实现。

请查看以下以面向对象编程（OOP）方式实现的Fenwick Tree数据结构的C++/Python/Java/OCaml实现：
fenwicktree_ds.cpp | py | java | ml

再次强调，您可以自由定制这个自定义库实现以适应您的需求。