树状数组：高效处理前缀和与单点更新

前缀和很强，但它有一个明显短板：一旦数组中的元素频繁变化，整张前缀和表维护起来就会很痛苦。也就是说，前缀和非常适合“静态多查询”，却不太适合“动态单点更新 + 区间查询”。

树状数组，通常也叫 Fenwick Tree，正是为了补上这个短板而出现的。它看起来名字里有个“树”，但实现上却往往只是一个数组。它真正巧妙的地方在于：

用一个特殊组织方式的数组，局部维护若干前缀区间和，从而让单点更新和前缀查询都能做到 O(log n)。

所以树状数组很适合被看成“动态版前缀和”的第一步。它没有线段树那么重，也没有平衡树那样复杂，但在适合的问题上非常高效、非常优雅。

一、树状数组想解决什么问题

最典型的问题通常是：

数组支持单点修改；
同时需要频繁求前缀和或区间和；
希望查询和更新都尽量快。

如果直接用普通数组：

单点更新是 O(1)；
区间和查询通常是 O(n)。

如果直接用前缀和：

查询很快；
但单点修改可能要连带更新后面大量前缀值。

树状数组正是在这两者之间找到了一个漂亮平衡：

更新不是常数；
查询也不是常数；
但两者都能压到 O(log n)。

二、树状数组为什么名字里有“树”

因为它虽然底层是数组，但数组中的每个位置并不是只对应一个单点，而是维护某一段区间的累计信息。这些区间之间形成了类似隐式树状覆盖关系。

换句话说：

它不是一棵显式画出来的二叉树；
但每个节点都像在管理某个区间；
整体区间分布有明显层次结构。

所以它叫树状数组，不是因为真的有左右孩子指针，而是因为：

区间信息的组织方式具有树形分层特征。

三、树状数组最关键的 lowbit 是什么

理解树状数组，最关键的入口通常是 lowbit(x)。

它表示：

一个整数二进制表示中，最低位的那个 1 所对应的值。

例如：

lowbit(6)，因为 6 二进制是 110，最低位 1 对应 2；
lowbit(8)，因为 8 二进制是 1000，结果是 8。

它的作用非常重要，因为树状数组正是用它来决定：

每个位置覆盖多长的区间；
更新时向哪些位置传播；
查询时如何分块回溯。

四、树状数组中每个位置维护的是什么

如果数组下标从 1 开始，那么树状数组 tree[i] 通常维护的是：

以 i 结尾；
长度为 lowbit(i)；
这一段连续区间的和。

例如某个位置可能维护：

一个单点；
或长度为 2 的小段；
或长度为 4、8 的更大段。

这些区间拼起来，就可以覆盖任意前缀。

这一步是树状数组最核心的认知：

它不是每个格子只存一个值，而是每个格子都存一个特殊长度的区间和。

五、树状数组为什么能快速求前缀和

求前缀和时，核心思路通常是：

从某个位置 x 开始；
把 tree[x] 加入答案；
然后跳到 x - lowbit(x)；
继续累加，直到变成 0。

这样做的本质是：

把一个大前缀拆成若干个不重叠的管理区间；
每次直接拿整段和，而不是一个个位置累加。

因为每次都能去掉一段最低位控制的区间，所以查询次数是对数级的。

六、树状数组为什么能快速更新单点

如果数组某个位置 x 增加了一个值，那么所有“覆盖到这个位置”的树状数组节点都必须同步更新。

更新时通常会：

先更新 tree[x]；
然后跳到 x + lowbit(x)；
再继续更新更高层覆盖区间；
直到越界。

这说明树状数组的更新本质上是：

从点出发；
沿着隐式结构一路把影响传播到更大区间。

所以它查询和更新都能保持在 O(log n)。

七、树状数组和前缀和到底是什么关系

可以把它理解成：

前缀和是静态一次性展开；
树状数组是动态地维护一组分层前缀块。

更直白一点：

前缀和把所有前缀结果都直接存好，所以查得最快；
树状数组只存部分分层区间结果，所以查和改都能兼顾。

这说明树状数组本质上不是在推翻前缀和，而是在补前缀和的动态更新短板。

八、树状数组适合什么问题

最典型的通常是：

单点更新；
前缀和查询；
区间和查询；
动态逆序对统计；
离散化后做频率前缀统计；
某些排名、计数、前缀贡献问题。

如果题目味道是：

点改；
前缀查；
区间和能转成两个前缀和相减；

那树状数组就很值得优先考虑。

九、树状数组和线段树怎么比较

这是一个非常经典的对比。

1. 树状数组

实现更简单；
常数通常更小；
特别适合前缀和 / 区间和类问题；
能处理的问题类型相对没那么广。

2. 线段树

功能更强；
能处理更复杂区间信息；
支持更丰富的更新和查询组合；
但实现更重。

所以很多时候可以先记一个经验：

如果只是前缀和、区间和、单点修改，树状数组通常是更轻巧的首选。

十、树状数组为什么常被说成“优雅”

因为它用一个看似普通的数组，就把：

分层区间；
动态更新；
对数级查询；
二进制结构；

非常漂亮地揉在了一起。

很多人第一次理解 lowbit 后，都会觉得它有一种“结构非常巧”的感觉。这种感觉其实很珍贵，因为它能让你真正体会到：

好的数据结构不一定外形复杂，关键在于信息组织方式是不是足够聪明。

十一、学习树状数组时最容易踩的坑

1. 只背模板，不理解 tree[i] 维护的区间是什么

这会导致一旦变形题就不会用了。

2. 不理解 lowbit 的作用

树状数组几乎所有跳转逻辑都围绕它。

3. 分不清“查询往左跳，更新往右跳”

这是实现中最常见的混淆点。

4. 把树状数组拿去处理不适合的问题

它很强，但不是所有区间结构都该用它。

总结

树状数组的重要性，不只是因为它常见，而是因为它非常漂亮地连接了“前缀和思想”和“动态维护”这两件事。真正值得先建立起来的，是这些核心认识：

树状数组本质上是一个分层维护区间和的数组结构；
lowbit 决定了每个位置覆盖的区间大小与跳转规律；
它可以在 O(log n) 时间内完成单点更新和前缀查询；
区间和查询本质上仍然是两个前缀和相减；
它比前缀和更适合动态更新，比线段树更轻量；
真正学会树状数组，不是会敲模板，而是理解“为什么一个点的变化会传播到这些区间块里”。

把这一篇理解透之后，后面再去学线段树时，你会更容易看出：树状数组是区间数据结构世界里非常优雅的第一站，而线段树则是在功能和表达能力上更进一步的扩展。

参考资源：