Fenwick 树 | Codeboy's Blog

形式陈述

设 $n\ge1$ ，数组 $a_1,\ldots,a_n$ 取值于阿贝尔群 $(G,\oplus,0)$ 。Fenwick 树用数组 $t[i]$ 保存长度

\operatorname{lowbit}(i)=i\mathbin{\&}(-i)

的后缀块

t[i] = a_{i-\operatorname{lowbit}(i)+1}\oplus\cdots\oplus a_i .

本页采用一基下标，查询允许 $0\le i\le n$ ，其中零前缀返回单位元；点更新要求 $1\le j\le n$ 。lowbit 按能容纳下标的无符号机器字运算计算，负号取模；更新时先检查 $\operatorname{lowbit}(j)>n-j$ ，若成立就停止，否则再相加，从而避免有限字长下的溢出。下标零不进入更新循环。

前缀查询从 $i$ 开始反复执行 $i\leftarrow i-\operatorname{lowbit}(i)$ ，按访问到的互不重叠块聚合；点增量 $a_j\leftarrow a_j\oplus\Delta$ 则反复执行 $j\leftarrow j+\operatorname{lowbit}(j)$ ，把 $\Delta$ 合入所有包含该位置的块。两者访问 $O(\log(n+1))$ 个槽并执行同阶群运算；元素与运算为常数成本时，得到同阶时间及 $O(n)$ 空间。空数组只接受空前缀查询。

由两个前缀可恢复区间聚合。加法记号下是 $P_r-P_{l-1}$ ；抽象群记号下是 $P_{l-1}^{-1}\oplus P_r$ 。标准点增量实现依赖交换性： $\Delta$ 在块内位于何处不再重要。

直觉

二进制最低位把每个前缀唯一拆成少量对齐块。查询向左删除当前最低位，恰好取出最后一个完整块；更新向右增加最低位，恰好枚举所有把该位置包含在其后缀块中的节点。它是一棵隐式树，父子关系编码在索引位模式中。

与线段树不同，Fenwick 树没有为每个区间保存显式左右孩子。紧凑布局换来更窄的操作接口：标准版本擅长可交换的点增量与前缀聚合，不自动支持任意非交换更新或复杂区间标签。

Fenwick 树中 lowbit 覆盖区间、查询 7 到 6 到 4 和更新 3 到 4 到 8 — Fenwick 树的隐式区间与操作路径

例子与边界

长度 $8$ 时，节点 $6=(110)_2$ 保存区间 $[5,6]$ ，节点 $8$ 保存 $[1,8]$ 。查询前缀 $7$ 访问 $7,6,4$ ，对应 $[7,7],[5,6],[1,4]$ ；这些块互不重叠且并为 $[1,7]$ 。更新位置 $3$ 访问 $3,4,8$ 。

若要把位置 $j$ 赋成新值 $v$ ，可在阿贝尔群中先求 $\Delta=a_j^{-1}\oplus v$ ，再执行点增量；实现还需知道旧值或通过查询恢复。只有交换幺半群而无逆元时，前缀查询可能仍有受限变体，但任意赋值与区间相减不再由标准接口保证。

对非交换群，块聚合有固定数组顺序，而把同一 $\Delta$ 直接合到块摘要的一端通常不能表示“在块中间修改一个元素”。存在针对特定操作的改造，并不使普通 BIT 成为任意群数据结构。区间最小值只在单调更新等受限场景有专门版本。

推论与应用

Fenwick 树实现动态前缀聚合、频数表和逆序对计数。若频数始终非负，前缀计数单调，还可沿二进制块定位给定累计秩，支持顺序统计；任意有正负抵消的群值不满足这项搜索前提。利用一个或两个树配合差分，可支持区间加与点查询、区间加与区间和；这些公式都依赖相应阿贝尔群与索引边界。

线段树只需幺半群即可维护有序区间聚合，并能通过更丰富节点摘要处理非交换操作；代价是更大的常数与显式树形分解。二者的 $O(\log n)$ 不代表代数前提和支持操作相同。

参考资料

Peter M. Fenwick, “A New Data Structure for Cumulative Frequency Tables,” Software: Practice and Experience 24(3), 1994, pp. 327–336.
OI-Wiki contributors, “Fenwick Tree,” 2026.

形式陈述 ​

反向链接

形式陈述