树状数组原理剖析：update向上与query向下的二进制本质

树状数组是很多算法初学者心里的“背了就忘”典型模板不长lowbit 一行update 一个循环query 一个循环当时看懂了过两天再写又卡住。最让人困惑的不是代码本身而是两个看起来不对称的方向更新走 i lowbit(i) 一路向上查询却走 i - lowbit(i) 一路向下凭什么两个方向最终都是 O(log n)先说结论update 和 query 方向不同不是因为树状数组故意设计成“一正一反”而是因为二进制的进位和消位本身就是两种不同过程。更新要沿着“父链”向上传播增量父链的构造规则就是把最低位的 1 往更高位推查询要把前缀拆成若干不重叠的完整小区间拆分规则就是逐次抹掉最低位的 1。理解了这两点树状数组不再是需要死背的模板而是一套可以从二进制推出来的结构。本文会从一个常见的动态前缀和问题切入把 lowbit 的作用、更新向上的原因、查询向下的原因、复杂度证明、完整代码、边界问题和进阶应用都讲清楚。无论你是刚接触数据结构的新手还是准备算法面试或竞赛的选手这篇文章都能帮你把树状数组彻底盘明白。1. 这篇文章真正要解决的问题先看一个算法题里出现频率极高的场景维护一个长度为 n 的数组支持两类操作。单点更新把某个元素 a[i] 加上一个值 delta。区间查询求区间 [l, r] 的和。这类问题出现在很多真实场景背后排行榜实时分数、在线人数统计、订单簿累积数量、逆序对计算、动态前缀频次统计本质上都是这个模型。朴素做法有两条路都不理想方案单点更新区间和查询普通数组O(1)O(n)维护前缀和数组O(n)O(1)线段树O(log n)O(log n)树状数组O(log n)O(log n)前缀和数组可以做到查询 O(1)但更新一个点之后后面所有前缀和都要重算最坏 O(n)。普通数组反过来更新很快查询很慢。线段树两个操作都能到 O(log n)但实现复杂度高节点数组、递归函数、区间合并都容易写错。树状数组的价值在于用非常短的代码把两个操作同时做到 O(log n)。它的缺点是不能像线段树那样支持任意区间合并操作比如区间最大值、区间懒更新但它的优势也很突出代码短、常数小、调试容易、空间占用少。很多教程到这里就开始贴模板导致读者只知道“怎么写”不知道“为什么这么写”。本文真正想解决的问题是三个update 为什么向上走query 为什么向下走这两个方向为什么都是 O(log n)把这三个问题想透树状数组就不会再背了又忘。2. 树状数组的核心每个下标管理一段区间树状数组的英文名是 Binary Indexed Tree通常简称 BIT。它的结构不复杂只有一个数组 bit下标从 1 开始使用。BIT 和普通数组最大的区别是bit[i] 保存的不是单一元素而是一个区间和这个区间由 i 的二进制最低位 1 决定。具体定义是bit[i] sum(a[i - lowbit(i) 1 .. i])其中 lowbit(i) 表示 i 的二进制最低位 1 对应的数值。例如i 3二进制是 011lowbit(3) 1所以 bit[3] 只保存 a[3]。i 4二进制是 100lowbit(4) 4所以 bit[4] 保存 a[1] a[2] a[3] a[4]。i 6二进制是 110lowbit(6) 2所以 bit[6] 保存 a[5] a[6]。把 n 8 的覆盖区间完整列出来会非常直观ii 的二进制lowbit(i)bit[i] 覆盖的区间100011[1, 1]200102[1, 2]300111[3, 3]401004[1, 4]501011[5, 5]601102[5, 6]701111[7, 7]810008[1, 8]可以观察到规律lowbit 越大接管的区间越大。所有 lowbit 为 1 的下标只保存单点lowbit 为 2 的下标保存长度为 2 的区间lowbit 为 4 的下标保存长度为 4 的区间。这个“按二进制划分区间”的设计是所有 BIT 操作的地基。更新时只有包含当前下标的位点需要修改查询时只要把目标前缀拆成若干个 BIT 位点覆盖的完整区间累加即可。3. lowbit 一行代码的本质找到最低位的 1lowbit 的求法是整个树状数组最核心的一行代码int lowbit(int x) { return x -x; }为什么按位与上相反数能得到最低位 1 的权值这要从补码说起。在补码表示中-x 等于 ~x 1。假设 x 12八位二进制是 00001100~x 11110011-x 11110100x -x 00001100 11110100 00000100 44 正好是 12 的最低位的 1 所在的二进制位权。原理可以这样理解补码会把 x 中最低位 1 右边的所有 0 变成 1把最低位 1 保留更高位全部取反。按位与之后只有最初那个“最低位的 1”会被保留其他位都会被抵消。除了 x -x也有人写成 x ~(x - 1)两者等价。这里有一个必须注意的坑x 不能为 0。如果 x 0lowbit 0更新循环会永远停在原地程序直接超时或卡死。这也是为什么树状数组所有下标从 1 开始下标 0 永远不参与运算。lowbit 的含义可以总结成一句话它既是 bit[i] 管理的区间长度又是 update 和 query 路径上每一步跳跃的步长。理解 lowbit树状数组就算理解了一半。4. 更新向上为什么是 i lowbit(i)更新操作要解决的问题是某个位置 a[i] 变了哪些 bit 节点需要跟着变答案很简单所有覆盖了下标 i 的节点都需要变。问题变成怎么高效找到这些节点。仍然以 n 8、更新 a[3] 为例。从覆盖表可以看到包含下标 3 的节点是 bit[3]、bit[4]、bit[8]。为什么不是 bit[6]因为 bit[6] 覆盖 [5, 6]不包含 3。为什么不是 bit[5]bit[5] 覆盖 [5, 5]也不包含。用 i lowbit(i) 模拟一次路径就出来了步当前 ilowbit(i)执行跳转后 i131bit[3] delta4244bit[4] delta8388bit[8] delta16超出 n 停止路径 3 - 4 - 8正好是所有包含 3 的节点。这不是巧合。看二进制3 0011lowbit(3) 1。3 1 4 0100相当于把最低位的 1 向高位进位。4 的 lowbit 是 44 4 8 1000再次进位。整个过程每次都是“消除当前最低位的 1并把进位保留到更高位”。为什么这个操作能找到父节点因为覆盖下标 i 的区间在二进制上一定是以某个更高的位作为区间边界的节点。父节点下标 id 必须满足 id 的覆盖区间 [id - lowbit(id) 1, id] 包含 i。通过 i lowbit(i) 向上进位会跳到更高一位的 1 所在位置这正是“当前覆盖区间的上一层管理者”。更新代码void update(int idx, long long delta) { for (; idx n; idx idx -idx) { bit[idx] delta; } }如果把 i lowbit(i) 改成 i - lowbit(i)更新会走到更小的兄弟节点而不是祖先。典型结果是 a[3] 只更新到 bit[3]bit[4] 和 bit[8] 永远不变后续区间查询结果错误。5. 查询向下为什么是 i - lowbit(i)查询要解决另一个方向的问题给出前缀位置 p如何用 BIT 里现有的完整区间拼出 [1, p] 的和。查询逻辑是从 p 开始每步累加 bit[p]然后 p - lowbit(p)直到 p 变成 0。拿 prefix(7) 举例步当前 ilowbit(i)累加的区间跳转后 i171bit[7] 覆盖 [7, 7]6262bit[6] 覆盖 [5, 6]4344bit[4] 覆盖 [1, 4]0累加的三个区间是 [7,7]、[5,6]、[1,4]拼起来正好是 [1,7]且不重不漏。从二进制再看7 0111。查询过程中0111去掉最低位 1得到 0110即 60110再去掉最低位 1得到 0100即 40100再去掉最低位 1得到 0000结束。每次 i - lowbit(i) 就是在二进制中抹掉最右边的一个 1。一个数的二进制中 1 的个数最多为 O(log n)所以查询一定是 O(log n)。查询代码long long prefix(int idx) const { long long res 0; for (; idx 0; idx - idx -idx) { res bit[idx]; } return res; } long long rangeSum(int l, int r) const { return prefix(r) - prefix(l - 1); }查询和更新看起来只是一个加一个减但本质不同update 是从单点向上找需要同步的祖先query 是从前缀端点向下拆出恰好覆盖目标区间的完整块。一个方向是“向所有包含我的节点传播”一个方向是“把一段前缀翻译成若干已有区间”。6. 完整示例树状数组实现单点更新与区间查询下面给出一个可以直接运行的 C 完整示例。代码使用 1-indexed 数组下标 0 不参与存储。// 文件路径FenwickDemo.cpp #include bits/stdc.h using namespace std; class Fenwick { private: int n; vectorlong long bit; public: Fenwick(int n) : n(n), bit(n 1, 0) {} // 单点更新a[idx] delta void update(int idx, long long delta) { for (; idx n; idx idx -idx) { bit[idx] delta; } } // 前缀和sum(a[1..idx]) long long prefix(int idx) const { long long res 0; for (; idx 0; idx - idx -idx) { res bit[idx]; } return res; } // 区间和sum(a[l..r]) long long rangeSum(int l, int r) const { if (l r) return 0; return prefix(r) - prefix(l - 1); } }; int main() { int n 8; vectorlong long a {0, 3, 1, 4, 1, 5, 9, 2, 6}; // 下标 1~8 Fenwick fw(n); for (int i 1; i n; i) { fw.update(i, a[i]); } cout prefix(5) fw.prefix(5) endl; cout rangeSum(3, 7) fw.rangeSum(3, 7) endl; fw.update(4, 10); // 把 a[4] 加上 10即 a[4] 变为 14 cout after update(4, 10) endl; cout rangeSum(3, 7) fw.rangeSum(3, 7) endl; cout rangeSum(1, 8) fw.rangeSum(1, 8) endl; return 0; }代码逻辑分三步初始化 Fenwick 对象bit 数组大小为 n 1避免下标越界。对下标 1 到 8 逐个调用 update完成建树。调用 prefix 和 rangeSum 验证查询结果再调用 update 验证更新传播。手算验证a[1..5] 3 1 4 1 5 14。a[3..7] 4 1 5 9 2 21。更新 a[4] 10 后a[4] 变成 14。a[3..7] 14 1 5 9 2 31。a[1..8] 3 1 14 1 5 9 2 6 41。7. 运行结果与效果验证编译并运行上面的程序g -stdc17 -O2 FenwickDemo.cpp -o FenwickDemo ./FenwickDemo预期输出prefix(5) 14 rangeSum(3, 7) 21 after update(4, 10) rangeSum(3, 7) 31 rangeSum(1, 8) 41如果输出和上面一致说明树状数组基本功能正确。想进一步验证推荐做这几件事写一个朴素 O(n) 前缀和数组随机生成数据后和 BIT 对拍。检查边界rangeSum(1, n) 应该等于数组总和rangeSum(i, i) 应该等于单点值。更新后立刻查询确认增量确实传播到了所有祖先节点。如果运行失败第一步先检查下标。绝大多数 BIT 运行异常不是算法错了而是把 0 传进了 update 或 prefix导致循环无法结束或结果偏小。Python 版本同样适合做原型验证# fenwick_demo.py class Fenwick: def __init__(self, n): self.n n self.bit [0] * (n 1) def update(self, idx, delta): while idx self.n: self.bit[idx] delta idx idx -idx def prefix(self, idx): res 0 while idx 0: res self.bit[idx] idx - idx -idx return res def range_sum(self, l, r): return self.prefix(r) - self.prefix(l - 1) if __name__ __main__: a [0, 3, 1, 4, 1, 5, 9, 2, 6] fw Fenwick(len(a) - 1) for i in range(1, len(a)): fw.update(i, a[i]) print(prefix(5) , fw.prefix(5)) print(rangeSum(3, 7) , fw.range_sum(3, 7)) fw.update(4, 10) print(after update(4, 10)) print(rangeSum(3, 7) , fw.range_sum(3, 7)) print(rangeSum(1, 8) , fw.range_sum(1, 8))运行python3 fenwick_demo.pyC 版本适合竞赛和高性能场景Python 版本适合快速验证逻辑。两份代码的输出应该完全一致。8. 常见问题与排查思路8.1 程序卡死或超时问题现象可能原因排查方式解决方案程序卡死或超时下标 0 传入 update / prefix检查循环入口 i 0 的情况使用 1-indexed循环前特判 idx 0结果偏小查询区间时用 rangeSum(l, r) prefix(l) - prefix(r)打印 prefix(l) 和 prefix(r)改成 prefix(r) - prefix(l - 1)更新没生效直接修改 bit 数组原值检查是否绕过 update统一通过 update 修改数值溢出int 不够