fenwick_tree]

我们应如何在内存中实际存储一棵删减后的线段树？如果我们仔细观察图 10，一种策略便显而易见：只需将每个活跃节点“向下滑动”并向右移动，直至其落入底层数组的一个空位中，如图 12 所示。这在活跃节点与范围 $1 \ldots n$ 内的索引之间建立了一一对应的关系。理解这种索引方案的另一种方式是使用树的后序遍历，跳过非活跃节点，并为遍历过程中遇到的活跃节点赋予连续的索引。我们也可以通过以“右倾”风格绘制树来可视化这一结果（图 13），将每个活跃节点与其存储位置所在的数组槽垂直对齐。

这种将删减后线段树中的活跃节点存储在数组中的方法，正是所谓的芬威克树。有时我也会称其为芬威克数组，意在特别强调其底层的数组数据结构。

诚然，这是一种巧妙的空间利用方式，但关键问题在于如何实现更新和区间查询操作。我们为线段树实现的这些操作，无论是直接在递归数据结构上操作，还是在树存储于数组中时通过对索引进行简单操作，都是通过递归地沿树向下遍历来完成的。然而，当将删减后树的活跃节点存储在芬威克数组中时，哪些数组索引上的操作能够对应于在树中移动，这并非先验可知。为攻克此难题，我们首先需要绕道进入一个用于处理二进制补码数值的领域特定语言。