Fenwick 树

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

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

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

Fenwick 树实现动态前缀聚合公理库前缀和Prefix sum · Cumulative sum预先累计序列前缀，使静态区间和查询可由两个前缀值相减得到。、频数表、逆序对计数和顺序统计。利用一个或两个树配合差分，可支持区间加与点查询、区间加与区间和；这些公式都依赖相应阿贝尔群与索引边界。

线段树公理库线段树Segment tree把区间递归分解为规范节点，并在每个节点保存幺半群聚合值的平衡树结构。只需幺半群即可维护有序区间聚合，并能通过更丰富节点摘要处理非交换操作；代价是更大的常数与显式树形分解。二者的 $O(\log n)$ 不代表代数前提和支持操作相同。