假设我们拥有一个包含 $n$ 个整数的序列 $a_1, a_2, \ldots, a_n$，并希望能够任意交错执行以下两种操作，如图 1 所示：

• 对任一给定索引 ¹ $i$ 处的数值，增加某个值 $v$。
• 求出任一给定区间 $[i, j]$ 内所有数值之和，即 $a_i + a_{i+1} + \cdots + a_j$。我们称此操作为区间查询。

注意，更新操作表述为将现有值增加 $v$；我们亦可通过增加 $v - u$ (其中 $u$ 为旧值) 来将给定索引处的值设为一个新值 $v$。

倘若我们仅将整数存储于一个可变数组中，那么更新操作可在常数时间内完成，但区间查询则需要与区间大小成线性关系的时间，因其必须遍历整个区间 $[i, j]$ 以累加其值。

为改善区间查询的运行时效，我们或可尝试缓存（至少部分）区间和。然则，此举必须审慎为之，因为在更新某个索引处的值时，相关的缓存和亦须保持同步更新。例如，一种直截了当的方法是使用一个数组 $P$，其中 $P_i$ 存储前缀和 $a_1 + \cdots + a_i$；$P$ 可通过一次扫描在常数时间内预计算得出。如此一来，区间查询便十分快捷：我们可通过计算 $P_j - P_{i-1}$ 在常数时间内获得 $a_i + \cdots + a_j$（为方便起见，我们设 $P_0 = 0$，如此该式即便在 $i=1$ 时亦能成立）。不幸的是，此时更新操作却需要线性时间，因为改变 $a_i$ 将导致对所有 $j \ge i$ 的 $P_j$ 进行更新。

是否存在一种数据结构，能够使这两种操作均在亚线性时间内完成？（在继续阅读下一段之前，您不妨稍作停顿，思考一番！）这并非仅仅是一个学术问题：该问题最初是在算术编码（Rissanen & Langdon, 1979; Bird & Gibbons, 2002）的背景下被提出的。算术编码是一类将消息转换为比特序列以供存储或传输的技术。为最大限度地减少所需的比特数，通常需要为出现频率较高的字符分配较短的比特序列，反之亦然；这就引出了维护一个动态字符频率表的需求。每当处理一个新字符时，我们就更新该表；而为了将单位区间细分为与各字符频率成比例的连续段，我们需要查询该表以获取累积频率（Ryabko, 1989; Fenwick, 1994）。

那么，我们能否使两种操作都在亚线性时间内完成呢？答案自然是肯定的。一种简单的技巧是将序列划分为 $\sqrt{n}$ 个桶，每个桶的大小为 $\sqrt{n}$，并创建一个大小为 $\sqrt{n}$ 的附加数组来缓存每个桶的和。更新操作仍然保持在 $O(1)$ 时间内，因为我们只需更新给定索引处的值以及相应桶的和。区间查询现在则可在 $O(\sqrt{n})$ 时间内完成：为求和 $a_i + \cdots + a_j$，我们手动累加从 $a_i$ 到其所在桶末尾的值，以及从 $a_j$ 所在桶开头到 $a_j$ 的值；对于所有介于两者之间的桶，我们则可以直接查找它们的和。

我们可以通过引入额外的缓存层级，以略微增加更新操作的开销为代价，进一步加快区间查询的速度。例如，我们可以将序列划分为 $\sqrt[3]{n}$ 个“大桶”，然后将每个大桶进一步细分为 $\sqrt[3]{n}$ 个“小桶”，每个小桶包含 $\sqrt[3]{n}$ 个值。每个桶的和都被缓存；现在每次更新需要修改三个值，而区间查询则在 $O(\sqrt[3]{n})$ 时间内完成。

以此类推，我们最终会得到一种基于二分治策略的区间和缓存方法，使得更新和区间查询操作的时间复杂度均为² $O(\log n)$ 。具体而言，我们可以构建一棵完全二叉树³，其叶节点存储序列本身，而每个内部节点则存储其子节点的和。（这对于许多函数式程序员而言应是一个耳熟能详的概念；例如，手指树（finger trees）（Hinze & Paterson, 2006; Apfelmus, 2009）便采用了类似的缓存机制。）由此产生的数据结构通常被称为线段树，⁴ 大抵是因为每个内部节点最终都缓存了底层序列的一个（连续）段的和。

图 2 展示了一棵基于长度为 $n=16$ 的示例数组构建的线段树（为简化起见，我们假设 $n$ 是 2 的幂，尽管将其推广到非 2 的幂的情况亦不难）。树的每个叶节点对应数组中的一个元素；每个内部节点都带有一个灰色条块，显示其所代表的底层数组段。

我们来看如何利用线段树来实现前面所述的两种操作，并使其均能在对数时间内完成。

• 要更新索引 $i$ 处的值，我们还需要更新包含该值的所有缓存区间和。这些恰好是沿着从索引 $i$ 处的叶节点到树根路径上的所有节点；这样的节点数量级为 $O(\log n)$。图 3 阐释了图 2 中示例线段树的更新过程；更新索引 5 处的条目仅需修改根节点到被更新条目路径上的阴影节点。
• 要执行区间查询，我们自顶向下遍历树，同时记录当前节点所覆盖的范围。
  • 若当前节点的范围完全包含在查询范围内，则返回当前节点的值。
  • 若当前节点的范围与查询范围不相交，则返回 0。
  • 否则，递归查询两个子节点，并返回结果之和。

图 4 阐释了计算区间 $[4 \ldots 11]$ 之和的过程。蓝色节点是我们递归遍历的节点；绿色节点是其范围完全包含在查询范围内、无需进一步递归而直接返回其值的节点；灰色节点则与查询范围不相交，返回零。本例中的最终结果是绿色节点值的总和，$1 + 1 + 5 + (-2) = 5$（不难验证，这确实是区间 $[4 \ldots 11]$ 内的值的和）。

在这个小例子中，看似我们访问了相当大比例的节点，但一般而言，我们访问的节点数量不会超过大约 $4 \log n$ 个。图 5 更清晰地展示了这一点。整棵树中最多只有一个蓝色节点可以拥有两个蓝色子节点，因此，树的每一层最多包含两个蓝色节点和两个非蓝色节点。我们实际上执行了两次二分查找，一次用于寻找查询区间的左端点，另一次用于寻找右端点。

线段树是解决该问题的一种颇为优良的方案：正如我们将在第 2 节中看到的那样，它们与函数式语言契合良好；同时它们也易于进行强大的泛化，例如支持惰性传播的区间更新以及通过共享不可变结构实现持久化更新历史（Ivanov, 2011b）。

芬威克树，或称二叉索引树（Fenwick, 1994; Ivanov, 2011a），是该问题的另一种解决方案。它们在通用性上有所欠缺，但在内存占用方面却极其精简——除了存储树中值的数组之外，几乎不需要任何额外空间——并且实现速度极快。换言之，它们非常适用于诸如底层编码/解码例程之类的应用场景，这些场景不需要线段树所能提供的任何高级特性，但却追求极致的性能。

class FenwickTree {
    private long[] a;
    public FenwickTree(int n) { a = new long[n+1]; }
    public long prefix(int i) {
        long s = 0;
        for (; i > 0; i -= LSB(i)) s += a[i]; return s;
    }
    public void update(int i, long delta) {
        for (; i < a.length; i += LSB(i)) a[i] += delta;
    }
    public long range(int i, int j) {
        return prefix(j) - prefix(i-1);
    }
    public long get(int i) { return range(i,i); }
    public void set(int i, long v) { update(i, v - get(i)); }
    private int LSB(int i) { return i & (-i); }
}

我们的目标，并非为此已解决的问题编写优雅的函数式代码。相反，我们的目标在于运用一种函数式的领域特定语言来处理位串，并结合等式推理，从第一性原理出发，推导并阐释这段令人费解的命令式代码——展示函数式思维与等式推理之力，即便用于理解以其他非函数式语言编写之代码亦能奏效。在对线段树（第 2 节）建立更深入的直觉之后，我们将看到芬威克树如何能被视为线段树的一种变体（第 3 节）。随后，我们将绕道探讨二进制补码表示法，开发一个适宜的位操作 DSL，并解释LSB函数的实现（第 4 节）。借助于该 DSL，我们将推导出在芬威克树与标准二叉树之间来回转换的函数（第 5 节）。最终，我们将能够推导出在芬威克树内部移动的函数：先将其转换为二叉树索引，执行显而易见的操作以实现二叉树内的预期移动，然后再转换回来。通过等式推理将转换过程融合消除，最终将揭示隐藏其后的LSB函数，一如预期（第 6 节）。