Fenwick Tree（二叉索引树）详解

1. 简介

Fenwick Tree，又称 Binary Indexed Tree (BIT)，是一种能够高效处理数组元素更新和范围求和查询的数据结构。它在处理动态范围求和问题时表现尤为出色，特别适用于需要频繁更新和频繁求和的场景。

本文将带你从零构建 Fenwick Tree，并通过代码示例掌握其核心操作：前缀和查询和单点更新。

2. 问题描述

我们面临的问题是：给定一个下标从 1 开始的数组 A = {A₁, A₂, ..., Aₙ}，支持以下两种操作：

**update(i, value)**：将数组 A 中第 i 个位置的值更新为 value。
**sum(left, right)**：计算数组 A 中从 left 到 right 的元素之和。

我们的目标是尽可能高效地实现这两个操作。

3. 暴力解法

最简单的方式是直接操作数组：

function update(i, value):
    A[i] = value

function sum(left, right):
    result = 0
    for i from left to right:
        result += A[i]
    return result

update：时间复杂度为 ✅ O(1)
sum：时间复杂度为 ❌ O(n)

适用于少量查询场景，但面对大量操作时效率低下。

4. 前缀和解法

为了优化求和操作，我们可以使用前缀和数组：

function prefixSum(A, n):
    prefix[0] = 0
    for k from 1 to n:
        prefix[k] = prefix[k - 1] + A[k]
    return prefix

然后，sum 操作可以变为：

function sum(left, right):
    return prefix[right] - prefix[left - 1]

而 update 操作则需要更新所有后续前缀和：

function update(i, value):
    delta = value - A[i]
    for k from i to n:
        prefix[k] += delta
    A[i] = value

sum：✅ O(1)
update：❌ O(n)

虽然 sum 变快了，但 update 变慢了，仍然不适合频繁更新的场景。

5. Fenwick Tree 解法

Fenwick Tree 能在 ✅ O(log n) 时间内完成 update 和 sum 操作，非常适合大规模数据操作。它本质上是一个树状结构，通过位运算来高效维护和查询前缀和。

5.1 责任范围（Range of Responsibility）

每个索引 i 在 Fenwick Tree 中维护一个特定区间的和，这个区间的长度由 最右边的 1（RSB） 决定。

例如：

索引 12 的二进制为 1100，RSB 是 100（即 4），因此它负责 A₉~A₁₂ 的和。
索引 7 的二进制为 0111，RSB 是 1，因此它只负责 A₇。

5.2 RSB 的计算

使用位运算可以快速获取一个数的 RSB：

function RSB(i):
    return i & (-i)

例如：

12 & -12 = 4
7 & -7 = 1

5.3 Fenwick Tree 结构

我们用一个数组 fenwick 来表示 Fenwick Tree：

fenwick[i] = sum of A[i - RSB(i) + 1 ... i]

比如：

fenwick[8] = A₁ + A₂ + ... + A₈
fenwick[12] = A₉ + A₁₀ + A₁₁ + A₁₂

通过树状结构可以清晰看到各个节点之间的覆盖关系。

5.4 Fenwick Tree 构建

构建 Fenwick Tree 的过程可以看作是从小到大传播 Fenwick 值的过程：

function constructFenwick(A, n):
    fenwick = A.clone()
    for i from 1 to n:
        parent = i + RSB(i)
        if parent <= n:
            fenwick[parent] += fenwick[i]
    return fenwick

时间复杂度：✅ O(n)

5.5 前缀和查询

要计算前缀和 prefixSum(i)，我们从 i 开始，不断减去 RSB，直到 0：

function prefixSum(i):
    result = 0
    while i > 0:
        result += fenwick[i]
        i -= RSB(i)
    return result

时间复杂度：✅ O(log n)

5.6 单点更新

更新某个位置的值时，我们需要向上更新所有受影响的 Fenwick 值：

function add(i, delta):
    while i <= n:
        fenwick[i] += delta
        i += RSB(i)

时间复杂度：✅ O(log n)

5.7 完整接口实现

结合以上函数，我们可以实现完整的 Fenwick Tree 接口：

function update(i, value):
    delta = value - A[i]
    add(i, delta)
    A[i] = value

function sum(left, right):
    return prefixSum(right) - prefixSum(left - 1)

update：✅ O(log n)
sum：✅ O(log n)

6. 总结

方法	update 时间复杂度	sum 时间复杂度	空间复杂度
暴力	❌ O(1)	❌ O(n)	✅ O(1)
前缀和	❌ O(n)	✅ O(1)	❌ O(n)
Fenwick Tree	✅ O(log n)	✅ O(log n)	✅ O(n)

✅ Fenwick Tree 是处理动态范围求和问题的首选方案，尤其适合频繁更新和频繁查询的场景。

核心思想：通过位运算快速定位责任范围，从而实现高效更新和查询。
应用场景：在线算法题、数据统计、频率统计、逆序对统计等。

💡 踩坑提醒：注意数组下标从 1 开始，否则 RSB 逻辑会出错。
⚠️ 调试建议：打印 fenwick 数组有助于理解 Fenwick Tree 的构建和更新过程。

如你所见，Fenwick Tree 是一个优雅而高效的数据结构，值得每一位算法爱好者掌握。

Persistence

REST

Security