树状数组

定义

树状数组(Binary Indexed Tree,又称 Fenwick Tree)是 Peter Fenwick 于 1994 年发表的数据结构,以一个与原数组等长的辅助数组隐式编码一棵树,支持 O(log n) 的单点修改与前缀和查询。

原理

核心是 lowbit 运算(x & -x,取二进制最低位的 1):下标为 i 的节点负责统计以 i 结尾、长度为 lowbit(i) 的区间和。查询前缀和时沿 i -= lowbit(i) 累加;更新时沿 i += lowbit(i) 传播。两个方向的跳跃各至多 log n 步。区间和由两个前缀和相减得到;配合差分数组可支持区间修改、单点查询。

应用

逆序对计数、动态排名统计、离线查询处理、二维扩展用于平面统计问题;在需要高频前缀聚合的工程场景(如实时排行榜)中也常见。

优缺点

代码仅十余行、空间 O(n)、缓存友好;但只能维护可差分的信息(如求和),灵活性不及线段树。