\ 考虑跟踪整数列表A的挑战。列表A的用户对执行两种类型的操作感兴趣：
\ (1) 更新A中任何元素的值，以及
(2) 计算某个子数组A[l..r]的总和。
\ 列表 A 的长度为O(N) ，类型 1 查询的数量为O(Q_1) ，类型 2 的查询数量为O(Q_2) 。除了正确执行程序之外，每个过程所花费的时间必须适当，以适应所有查询。
\
:::info示例：考虑以下整数列表 A = [1, 2, 3, 4, 5]。
用户请求类型 1 查询以将 A 的第二个元素增加 3。这导致更新的列表 A = [1, 5, 3, 4, 5]。用户的下一个请求是求 A[1..3] 中元素的总和。该值计算为 9。
:::
\ 挑战的本质是确定满足这些需求的最佳数据结构。一个很好的选择是 Fenwick 树，它为每个查询（更新和范围查询）花费对数时间。本文的其余部分将探讨这个有趣的数据结构背后的概念。
第一次尝试解决方案
让我们调查一些可能的解决方案。非常自然的解决方案是只保留整数列表A的原始形式。任何更新查询都可以快速轻松地处理。由于更新查询需要更改A的元素，因此可以在O(1)时间内处理该请求。另一方面，求和查询取决于请求的间隔长度。每次进行类型 2 查询时，都必须通过迭代范围来计算总和。在最坏的情况下，范围求和查询可能需要O(N) 。当类型 2 查询的数量较少时，该策略将有效地发挥作用。然而，随着类型 2 查询数量的增加，整体时间复杂度变为O(Q_2.N) 。这本质上是二次的，因此是不可取的。
\
:::tip 当更新较多且范围求和查询较少时，仅维护列表 A 即可解决问题。
:::
\ 但是如果Q2很大怎么办？我们希望加快范围求和查询。简单的观察表明，任何子数组和都可以表示为前缀和的差。这是它的计算方式 –
\
sum(A[l..r]) = sum(A[0..r]) - sum(A[0..l-1])
\ 因此，如果我们预先计算了前缀和，则可以在O(1)时间内处理范围子查询。基于这个想法，让我们为数组A维护一个前缀和数组P 。现在可以使用列表P中存在的值来回答任何范围查询。但这使得更新操作成本高昂。请注意对A[i]值的任何更改将如何导致我们重新计算P中大于或等于i的所有位置的条目。因此，在最坏的情况下，更新操作可能需要O(n)时间。
\
:::tip 当更新操作的数量少于范围查询的数量时，维护一个前缀数组是一种有效的解决方案。
:::
\ 我们刚刚看到的是所有可能解决方案的两个极端。 Fenwick 树维护所有这些数据的方式允许我们在O(logn)时间内回答这两种类型的查询。
芬威克树的基本思想
Fenwick Tree 的想法是维护一个列表T 。列表T的长度与列表A的长度相同。列表中的每个元素T[i]存储A在g(i)到i范围内的元素之和。其中g(i)在[0, i]范围内。因此函数g(.)有很多选择。创建列表T后，我们可以处理查询以找到前缀A[0..r]的总和，如下面的过程所示。
\
def sum(r): # Sum from A[0...r] s = 0 while r >= 0: s = s + T[r] r = g(r) - 1 return s
\ 对于更新查询，需要更新列表 T 以适应pos索引处元素delta的增加。因此，更新查询将影响T中范围包含pos的那些索引j 。以下过程总结了相同的内容。
\
def update(pos, delta): for all j where g(j) <= pos <= j: T[j] += delta return
\ 选择函数g()是最后一块拼图。相同功能的明智选择有助于实现 Fenwick Tree 的边界。
:::tip 当g(i)=0时，列表T归结为前缀总和。并且，当g(i)=i时，列表T变得完全等于列表A 。
:::
\
Fenwick 树中函数 g() 的选择
以下函数g()的选择是在 Fenwick Tree 中进行的。它被定义为g(i)是通过翻转数字i的所有尾随零获得的数字。换言之，当从最低有效位 (LSB) 移动到最高有效位 (MSB) 直到获得零时，通过将所有 1 转换为零来获得 g(i)。这个函数可以用按位运算符很好地写成g(i) = i & (i + 1) 。
\
:::info示例 – 粗体数字为二进制
g(8) = g( 1000 ) = 1000 = 8
g(7) = g( 111 ) = 000 = 0
g(23) = g( 10111 ) = 10000 = 16
:::
\ 因此，我们拥有处理求和查询所需的所有详细信息。但是在实现更新方法方面仍然存在障碍。我们如何找到列表T中受更新操作影响的所有位置？需要注意的是，在将尾随 1 转换为 0 之后，列表T中任何小于或等于正在更新的位置pos的位置也必然会被更新。所有这些数字都可以通过用1替换最不重要的零来生成。继续此过程将导致所有将受更新查询影响的位置。这也有一个直接函数，它可以如下给出 – h(j) = j | (j + 1)
\
:::信息示例
pos = 5。因此T[5]将被更新。
h(5) = h( 101 ) = 111 = 7。因此T[7]将被更新。
h(8) = h( 111 ) = 1111 = 15。因此T[15]将被更新。
……
:::
\ 这也完成了拼图的最后一块。现在可以在O(log n)时间内回答这两个查询。接下来我们将看到这种说法的非正式证据。
\
理解时间复杂度
首先，让我们采用 sum 方法。对于任何范围， [0, r]我们从r移动到g(r)-1到g(g(r))-1等等，直到我们达到0 。考虑一个数字n ，其最低有效位 (LSB) 为零。如果数字 n 在其二进制表示中没有任何 1，我们就完成了。所以假设数字 n 在左起ith位有一个 1。数字 n 的类型为n = b_1 b_2 b_3 … b_(i-1) 1 0 0 0 … 0 ，其中b_1, b_2, …, b_(i-1)为0或1 。由于没有尾随，我们将有g(n) = n 。因此，我们将在循环期间从n移动到n-1 。数字n-1将具有以下二进制表示n-1 = b_1 b_2 b_3 … b_(i-1) 0 1 1 1 … 1 。请注意， g(n-1)看起来像g(n-1) = b_1 b_2 b_3 … b_(i-1) 0 0 0 0 … 0 。因此，只需 2 步，数字 n 中最右边的设置位就被取消设置。并且由于一个数字中最多可以有 log n 个设置位，因此循环将以对数步数终止。
\ 如果数字已经有尾随零，那么每一步也将取消设置最右边的设置位。因此，整个过程必然会以对数步数停止。
\
结论
使用 Fenwick Tree 处理点更新和范围求和查询是使用这种有趣的数据结构的众多应用之一。 Fenwick Tree 的许多实现都可以在 Internet 上找到。一个这样的可以在这里找到。为了进一步阅读，鼓励读者参考作者在撰写本文时参考的以下资源。
\ 有了这个有趣的数据结构，你可以解决很多有趣的问题。你知道任何其他的数据结构也可以用来解决这个问题吗？请在评论中回答！
\
原文： https://hackernoon.com/fenwick-tree-explained?source=rss