二进制索引（Fenwick）树是一种数据结构，为实现动态累积频率表提供了高效的方法。
这种Fenwick树数据结构使用了许多位操作技术。在这个可视化中，我们将使用Fenwick树这个术语来指代这种数据结构（通常缩写为'FT'），因为二进制索引树的缩写'BIT'通常与常见的位操作相关联。
Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
If you are an NUS student and a repeat visitor, please login.
假设我们有一个整数的多重集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。
| 索引/分数/符号 | 频率 f | 累积频率 cf |
|---|---|---|
| 0 | - | - (忽略索引0) |
| 1 | 0 | 0 |
| 2 | 1 | 1 |
| 3 | 0 | 1 |
| 4 | 1 | 2 |
| 5 | 2 | 4 == cf[4]+f[5] |
| 6 | 3 | 7 == cf[5]+f[6] |
| 7 | 2 | 9 |
| 8 | 1 | 10 |
| 9 | 1 | 11 |
| 10 == m | 0 | 11 == n |
Pro-tip 1: Since you are not logged-in, you may be a first time visitor (or not an NUS student) who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown]/[PageUp] to go to the next/previous slide, respectively, (and if the drop-down box is highlighted, you can also use [→ or ↓/← or ↑] to do the same),and [Esc] to toggle between this e-Lecture mode and exploration mode.
有了这样的累积频率表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）。
| 索引/分数/符号 | 频率 f | 累积频率 cf |
|---|---|---|
| 0 | - | - (忽略索引0) |
| 1 | 0 | 0 |
| 2 | 1 | 1 |
| 3 | 0 | 1 |
| 4 | 1 | 2 == rsq(1, 4) |
| 5 | 2 | 4 |
| 6 | 3 | 7 |
| 7 | 2 | 9 |
| 8 | 1 | 10 |
| 9 | 1 | 11 == rsq(1, 9) |
| 10 == m | 0 | 11 == n |
Pro-tip 2: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2021). We recommend using Google Chrome to access VisuAlgo. Go to full screen mode (F11) to enjoy this setup. However, you can use zoom-in (Ctrl +) or zoom-out (Ctrl -) to calibrate this.
动态数据结构需要在查询之间支持（频繁的）更新。例如，我们可能会更新（增加）分数7的频率从2 → 5（例如，又有3个学生得分7）并更新（减少）分数9的频率从1 → 0（例如，之前得分9的1个学生被发现抄袭作业，现在被罚为0，即，从分数中移除），从而更新表格为：
| 索引/分数/符号 | 频率 f | 累积频率 cf |
|---|---|---|
| 0 | - | - (忽略索引0) |
| 1 | 0 | 0 |
| 2 | 1 | 1 |
| 3 | 0 | 1 |
| 4 | 1 | 2 |
| 5 | 2 | 4 |
| 6 | 3 | 7 |
| 7 | 2 → 5 | 9 → 12 |
| 8 | 1 | 10 → 13 |
| 9 | 1 → 0 | 11 → 13 |
| 10 == m | 0 | 11 → 13 == n |
用纯数组基础数据结构来实现这个动态累积频率表将需要O(m)的更新操作。我们能做得更好吗？
Pro-tip 3: Other than using the typical media UI at the bottom of the page, you can also control the animation playback using keyboard shortcuts (in Exploration Mode): Spacebar to play/pause/replay the animation, ←/→ to step the animation backwards/forwards, respectively, and -/+ to decrease/increase the animation speed, respectively.
介绍：Fenwick 树数据结构。
在这个可视化中，Fenwick 树有三种使用模式。
第一种模式是默认的 Fenwick 树，它可以在 O(log n) 中处理点更新 (PU)和范围查询 (RQ)，其中 n 是数据结构中最大的（整数）索引/键。请记住，数据结构中实际的键数由另一个变量 m 表示。我们将这种默认类型简称为 PU RQ，即点更新范围查询。
这种巧妙的整数键排列思想最初出现在Peter M. Fenwick 的 1994 年论文中。
您可以点击'创建'菜单来创建一个频率数组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功能）。
尽管从概念上讲，这个数据结构是一个树，但它将被实现为一个名为ft的整数数组，范围从索引1到索引n（我们牺牲了我们的ft数组的索引0）。上面显示的Fenwick树的（黑色轮廓和白色内部）顶点中的值是存储在基于1的Fenwick树ft数组中的值。
目前，这个Fenwick树的边还没有显示出来。树有两个版本，查询树和更新树。
底部（蓝色内部）顶点内的值是频率数组 f 的值。
在数组ft中索引i存储的值（Fenwick树中的顶点i），即ft[i]，是键范围[i-LSOne(i)+1 .. i]的累积频率。在视觉上，这个范围由Fenwick树（查询/查询版本）的边缘显示。
关于LSOne(i) = (i) & -(i)操作的复习，请参见我们的位掩码可视化页面。
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。
ft[6] = 5 存储了键在 [6-LSOne(6)+1 .. 6] 中的累积频率。
(沿着从索引6向上回到索引4的边，再加1个索引)。
这是 [6-2+1 .. 6] = [5 .. 6] 和 f[5]+f[6] = 2+3 = 5。
函数 rsq(j) 返回从第一个索引 1（忽略索引 0）到索引 j 的累积频率。
这个值是存储在数组 ft 中与 j 相关的子频率之和，关系公式为 j' = j-LSOne(j)。这种关系形成了一个Fenwick树，具体来说，是Fenwick树的'询问树'。
我们将这个公式反复应用，直到 j 为0。
无论 n 的值如何，这个函数的运行时间都是 O(log m)。讨论：为什么？
我们之前已经看到 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。
rsq(i, j) 返回从索引 i 到 j（包含）的累积频率。
如果 i = 1，我们可以像之前那样使用 rsq(j)。
如果 i > 1，我们只需要返回：rsq(j) – rsq(i–1)（包容-排斥原理）。
讨论：你理解原因吗？
这个函数也在 O(log m) 中运行，无论 n 如何。讨论：为什么？
rsq(4, 6) = rsq(6) – [下一张幻灯片...]。
我们之前已经看到rsq(6) = ft[6]+ft[4] = 5+2 = 7。
rsq(4, 6) = rsq(6) – rsq(3)。
我们可以类似地计算出rsq(3) = ft[3]+ft[2] = 0+1 = 1。
要更新键（索引）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如何。讨论：为什么？
Fenwick 树的第二种模式是可以处理范围更新 (RU)，但只能以 O(log n) 处理点查询 (PQ)。
我们将此类型缩写为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。
顶部的顶点显示了存储在Fenwick树中的值（ft数组）。
底部的顶点显示了数据的值（频率表f）。
注意到这种RU PQ类型中使用的Fenwick树的巧妙修改：我们将范围的开始增加+1，但将范围结束后的一个索引减少-1以达到这个结果。
Fenwick 树的第三种模式是可以同时处理范围更新 (RU)和范围查询 (RQ)的模式，其时间复杂度为 O(log n)，使得这种类型与具有懒惰更新的线段树相当，后者也可以在 O(log n) 的时间复杂度内进行 RU RQ。
创建数据并尝试在其上运行范围更新或范围查询算法。
创建数据是插入几个间隔，类似于 RU PQ 版本。但是这次，你也可以高效地进行范围查询。
在范围更新范围查询 Fenwick 树中，我们需要有两个 Fenwick 树。顶部的顶点显示第一个 Fenwick 树的值（BIT1[] 数组），中间的顶点显示第二个 Fenwick 树的值（BIT2[] 数组），而底部的顶点显示数据的值（频率表）。第一个 Fenwick 树的行为与 RU PQ 版本相同。第二个 Fenwick 树用于进行巧妙的偏移，以再次允许范围查询。
我们有一些涉及此数据结构的额外内容。
遗憾的是，截至2020年，这种数据结构在C++ STL、Java API、Python或OCaml标准库中尚未提供。因此，我们必须编写我们自己的实现。
请查看以下以面向对象编程（OOP）方式实现的Fenwick Tree数据结构的C++/Python/Java/OCaml实现：
fenwicktree_ds.cpp | py | java | ml
再次强调，您可以自由定制这个自定义库实现以适应您的需求。
You have reached the last slide. Return to 'Exploration Mode' to start exploring!
Note that if you notice any bug in this visualization or if you want to request for a new visualization feature, do not hesitate to drop an email to the project leader: Dr Steven Halim via his email address: stevenhalim at gmail dot com.
新建 - O(m log m)
新建 - O(m)
RSQ(i, j)
更新(i, v)