形式陈述

Fenwick 树以数组 $t[i]$ 保存长度为 $\mathrm{lowbit}(i)=i\mathrm{\&}(-i)$ 的后缀块聚合。 前缀查询反复执行 $i\leftarrow i-\mathrm{lowbit}(i)$；单点增量更新反复执行 $i\leftarrow i+\mathrm{lowbit}(i)$。两者均访问 $O(\log n)$ 个节点，空间 $O(n)$。 若操作构成交换群，可由两个前缀查询得到任意区间值。

直觉

二进制最低位决定索引所代表的最大对齐块；查询向左拆块，更新向右通知所有包含该点的块。

例子与边界

它可维护动态频数并通过二进制提升查找第 $k$ 个前缀位置。一般非交换操作、任意区间赋值或复杂懒更新并不适合普通 Fenwick 树。

推论与应用

用于动态前缀和、逆序对、在线频数、坐标压缩后的统计和顺序统计。

参考资料

• Peter M. Fenwick, A New Data Structure for Cumulative Frequency Tables (1994), original cumulative-frequency structure.
• OI-Wiki contributors, OI-Wiki (2026), Fenwick tree.