树状数组详解：从lowbit原理到单点更新与前缀查询实战

之前在刷算法题和准备面试的过程中树状数组Binary Indexed Tree一直是一个“背模板能写但不深究就讲不清原理”的数据结构。尤其是lowbit、更新向上、查询向下这三句话很多资料直接抛出来却不解释为什么要这么做。等你真的去思考i lowbit(i)和i - lowbit(i)背后的二进制规律时才会发现树状数组其实是一个非常精巧的设计。这篇文章想把树状数组的底层逻辑完整拆开围绕lowbit这条主线讲清楚单点更新为什么向上走前缀查询为什么向下走以及为什么这两个操作都能稳定在 O(log n)。同时我会结合完整代码示例、运行结果和题目场景逆序对、树状数组上二分让新手也能从 0 到 1 掌握这个数据结构。文章中的代码以 C 和 Python 为主核心模板可以直接复制到你的工程或竞赛代码中使用。1. 背景与核心概念树状数组到底解决了什么问题1.1 从一个简单需求说起假设你现在维护一个长度为 n 的整数数组需要支持两类操作修改某个位置上的元素值。查询前 i 个元素的和也就是前缀和。如果使用普通数组操作时间复杂度说明单点修改O(1)直接赋值前缀查询O(n)从 1 扫到 i 累加如果使用前缀和数组操作时间复杂度说明单点修改O(n)需要同步更新后面所有前缀和前缀查询O(1)直接返回 pre[i]可以看到普通数组和前缀和数组都只能“一边快”。一旦数据规模达到 10^5、10^6且操作次数很多时O(n) 的代价就不可接受了。树状数组就是在这个背景下产生的它用一组树状结构维护区间和让单点修改和前缀查询的复杂度同时变成 O(log n)。1.2 树状数组中的几个关键名词原始数组 a[1..n]下标从 1 开始。树状数组 c[1..n]c[i] 并不是存储 a[i] 本身而是存储某个区间[i - lowbit(i) 1, i]的和。lowbit(i)表示 i 的二进制表示中最低位的 1 及其后面所有 0 组成的数值。例如lowbit(6) 2因为 6 的二进制是 110最低位 1 在第 1 位从 0 开始计数值是 2。lowbit(8) 8因为 8 的二进制是 1000最低位 1 在第 3 位值是 8。lowbit(5) 1因为 5 的二进制是 101最低位 1 在第 0 位值是 1。1.3 树状数组的适用场景树状数组最经典的场景包括单点更新、区间求和前缀和。区间更新、单点查询配合差分技巧。求逆序对数量。动态维护有序集合中第 k 小元素。二维树状数组处理子矩阵求和问题。它和线段树相比优点是代码短、常数小、实现简单缺点是适用的操作范围相对固定比如区间最值问题用树状数组就比较麻烦。因此在很多算法竞赛和面试题中树状数组是优先考虑的“轻量级”数据结构。2. 环境准备与代码模板先搭好可运行的框架2.1 示例环境说明本文示例以常见环境为例重点演示代码思路版本不需要过于纠结C需要支持 C11 及以上标准推荐使用 g 编译。Python需要 Python 3.6 及以上版本。调试方式本地命令行编译运行或直接在在线评测平台提交。C 编译命令示例g -stdc11 -O2 -o bit bit.cpp ./bitPython 运行命令示例python3 bit.py2.2 工程文件结构为了演示方便建议把封装好的树状数组单独放在一个类或结构体中。示例结构如下tree_array_demo/ ├── bit.cpp # C 完整示例 ├── bit.py # Python 完整示例 └── README.md # 说明文件2.3 为什么下标从 1 开始树状数组的经典实现中原数组 a 和树状数组 c 都从下标 1 开始使用。这不是为了刁难新手而是因为lowbit的相关计算在正数下标上更简洁。如果下标从 0 开始i - lowbit(i)可能会让索引变成负数反而增加边界判断。所以本文统一按下标从 1 开始处理。下面先给出核心模板。C 版本// 文件路径bit.cpp #include bits/stdc.h using namespace std; class FenwickTree { private: vectorint tree; int n; int lowbit(int x) { return x -x; } public: FenwickTree(int size) : n(size) { tree.resize(n 1, 0); } // 单点更新给位置 idx 增加 delta void add(int idx, int delta) { while (idx n) { tree[idx] delta; idx lowbit(idx); } } // 前缀查询查询 [1, idx] 的和 int query(int idx) { int res 0; while (idx 0) { res tree[idx]; idx - lowbit(idx); } return res; } }; int main() { vectorint a {0, 1, 3, 5, 7, 9, 11}; int n 6; FenwickTree bit(n); for (int i 1; i n; i) { bit.add(i, a[i]); } cout sum[1..4] bit.query(4) endl; cout sum[2..6] bit.query(6) - bit.query(1) endl; return 0; }预期输出sum[1..4] 16 sum[2..6] 35Python 版本# 文件路径bit.py class FenwickTree: def __init__(self, n): self.n n self.tree [0] * (n 1) def lowbit(self, x): return x -x def add(self, idx, delta): while idx self.n: self.tree[idx] delta idx self.lowbit(idx) def query(self, idx): res 0 while idx 0: res self.tree[idx] idx - self.lowbit(idx) return res a [0, 1, 3, 5, 7, 9, 11] n 6 bit FenwickTree(n) for i in range(1, n 1): bit.add(i, a[i]) print(sum[1..4] , bit.query(4)) print(sum[2..6] , bit.query(6) - bit.query(1))运行结果与 C 版本一致。这段模板是整个树状数组的核心后面所有实战案例都基于它展开。3. 核心原理拆解lowbit 到底是什么3.1 lowbit 的数学定义lowbit(x)定义为在整数 x 的二进制表示中保留最低位的 1并将其右侧所有位都置 0 后得到的数值。例如x二进制lowbit(x)二进制表示100110012010201030111001410041005101100161102010711110018100081000从表里能看出一个直观规律lowbit(x)的结果一定是 2 的幂次因为它的二进制形式只有一个 1。3.2 用位运算实现 lowbitint lowbit(int x) { return x -x; }这里的关键在于负数的补码表示。在计算机中-x等于~x 1也就是把 x 的每一位取反再加 1。当你对 x 和 -x 做按位与时x 中比最低位 1 更高的所有位都会和 -x 的对应位相反结果为 0而最低位 1 及右侧的 0 会被原样保留。举个例子x 6 时x 000...0110 -x 111...1010 x -x 000...0010 2所以x -x得到的正是lowbit(x)。这也是树状数组中最核心的一行代码。3.3 lowbit 在树状数组中的角色树状数组中每个节点 c[i] 负责的区间长度恰好是lowbit(i)区间范围是[i - lowbit(i) 1, i]。举例说明c[4] 负责 [4 - 4 1, 4] [1, 4]。c[6] 负责 [6 - 2 1, 6] [5, 6]。c[7] 负责 [7 - 1 1, 7] [7, 7]。这种“按二进制最低位 1 决定覆盖范围”的方式让树状数组的所有操作都可以通过不停移动最低位 1 来完成。只要理解了这个覆盖关系后续的“更新向上、查询向下”就很容易想通。4. 单点更新为什么必须向上走4.1 更新操作要解决什么问题当我们修改 a[i] 时所有维护的区间包含 i 的 c[j] 都需要更新。问题在于怎么快速找到这些 c[j]答案就是反复执行j j lowbit(j)从 i 本身开始每次把最低位的 1 向左移动直到超过 n。4.2 一次完整更新过程假设 n 8现在要执行add(3, delta)也就是给 a[3] 增加 delta。更新路径如下j 3 lowbit(3) 1所以下一个 j 3 1 4 lowbit(4) 4所以下一个 j 4 4 8 lowbit(8) 8所以下一个 j 8 8 16 16 n停止最终更新的节点是 c[3]、c[4]、c[8]。为什么是这三个节点因为c[3] 负责 [3, 3]显然包含 3。c[4] 负责 [1, 4]包含 3。c[8] 负责 [1, 8]包含 3。再验证一个例子add(5, delta)。j 5 lowbit(5) 1下一个 j 6 lowbit(6) 2下一个 j 8 8 n 停止更新的节点是 c[5]、c[6]、c[8]。检查覆盖区间c[5] 负责 [5, 5]包含 5。c[6] 负责 [5, 6]包含 5。c[8] 负责 [1, 8]包含 5。规律成立。4.3 为什么i lowbit(i)能找到所有包含 i 的区间核心秘密在二进制。当执行i lowbit(i)时其实是在把 i 二进制中的最低位 1 向更高位进位。例如i 3 二进制 011 lowbit 1 二进制 001 3 1 4 二进制 100 i 5 二进制 101 lowbit 1 二进制 001 5 1 6 二进制 110 lowbit(6) 2 二进制 010 6 2 8 二进制 1000每一次进位新的 i 的“最低位 1”的位数都会至少提高 1 位。这样的节点数量最多等于二进制位数也就是 O(log n)。因此单点更新的复杂度是 O(log n)。4.4 更新方向的记忆技巧很多初学者会把add写反写成i - lowbit(i)。这里给一个记忆方法单点更新是“向上传递变化”。你修改了叶子节点 a[i] 之后所有覆盖它的上一层节点都要跟着改。在树状数组的二进制视角里上一层节点就是通过不断向右上方的进位得到的所以用。C 实现void add(int idx, int delta) { while (idx n) { tree[idx] delta; idx lowbit(idx); } }Python 实现def add(self, idx, delta): while idx self.n: self.tree[idx] delta idx self.lowbit(idx)5. 前缀查询为什么必须向下走5.1 查询操作要解决什么问题查询前缀和sum[1..i]时需要把区间 [1, i] 拆成若干段互不重叠的“树状数组节点”然后把这些节点的值累加起来。问题是如何高效拆分答案就是反复执行i i - lowbit(i)从 i 本身开始每次消去最低位的 1直到 i 变成 0。5.2 一次完整查询过程沿用 n 8 的例子查询sum[1..7]i 7 lowbit(7) 1累加 c[7]i 7 - 1 6 lowbit(6) 2累加 c[6]i 6 - 2 4 lowbit(4) 4累加 c[4]i 4 - 4 0 停止最终累加的节点是 c[7]、c[6]、c[4]。用区间覆盖展开c[7] 负责 [7, 7] c[6] 负责 [5, 6] c[4] 负责 [1, 4]合起来正好是 [1, 7]没有重叠也没有遗漏。再验证查询sum[1..6]i 6 累加 c[6]i 6 - 2 4 累加 c[4]i 4 - 4 0c[6] 覆盖 [5, 6]c[4] 覆盖 [1, 4]合计 [1, 6]。5.3 为什么i - lowbit(i)能拆分区间从二进制角度看i - lowbit(i)相当于把 i 二进制中最右侧的 1 直接改成 0。例如i 7 二进制 111 i - 1 6 二进制 110 消掉最低位 1 i 6 二进制 110 i - 2 4 二进制 100 消掉最低位 1 i 4 二进制 100 i - 4 0 二进制 000 消掉最低位 1每次消去一个 1区间 [1, i] 就被拆掉一块由lowbit(i)长度覆盖的区间。二进制中 1 的个数有限最多是 O(log n) 个所以查询复杂度也是 O(log n)。5.4 查询方向的记忆技巧查询和更新方向相反用的是-。可以这样记查询前缀和时你现在所处的位置代表“还剩下 [1, i] 这段没统计完”。你当前节点 c[i] 自己覆盖了最右侧的lowbit(i)个元素把这些元素加起来之后剩下的问题变成了查询 [1, i - lowbit(i)]所以 i 向左下走。C 实现int query(int idx) { int res 0; while (idx 0) { res tree[idx]; idx - lowbit(idx); } return res; }Python 实现def query(self, idx): res 0 while idx 0: res self.tree[idx] idx - self.lowbit(idx) return res6. 复杂度分析O(log n) 到底是怎么来的6.1 更新操作的操作次数上界在add过程中每次i lowbit(i)会让最低位 1 的位置向左移动。我们可以这样理解如果 i 的二进制有 k 位那么最低位 1 最多只能从第 0 位移动到第 k-1 位进位次数不超过 k。n 的二进制位数是log2(n) 1因此更新的操作次数是 O(log n)。6.2 查询操作的操作次数上界在query过程中每次i - lowbit(i)会消去二进制中最低位的一个 1。一个数的二进制表示中最多有log2(n) 1个 1因此查询的操作次数也是 O(log n)。6.3 通过一个小实验观察操作次数可以在代码里加一个计数器验证add(3, delta)在 n 100000 时到底执行了几次。int cnt 0; int idx 3; while (idx 100000) { idx idx -idx; cnt; } cout cnt endl;输出一次 run 就知道这个值远小于 100000通常只有十几到二十几次。这就是 O(log n) 的直观体验。6.4 建树的 O(n) 方法如果从空树开始对每个位置执行add(i, a[i])建树复杂度是 O(n log n)。对于大多数题目来说已经足够快。但如果 n 特别大可以用更巧妙的 O(n) 建树方法// 先直接把 a[i] 放入 c[i] for (int i 1; i n; i) { c[i] a[i]; } // 向上累加给父节点 for (int i 1; i n; i) { int parent i (i -i); if (parent n) { c[parent] c[i]; } }这个方法的核心是每个 c[i] 先保存叶子值然后一层层地向上累加。总操作次数是 n n/2 n/4 ... O(n)。7. 完整实战案例用树状数组求逆序对数量7.1 题目描述与思路给定一个数组求其中逆序对的数量。所谓逆序对是指满足i j且a[i] a[j]的数对。经典做法很多比如归并排序。使用树状数组也很方便步骤是对原数组离散化把数值映射到1..m的排名范围。从右往左扫描数组。每次扫描到一个元素 x先查询已经出现过的、值小于 x 的元素个数即query(x - 1)。将这个 x 的出现次数加 1执行add(x, 1)。因为是从右往左扫描所以已经出现过的元素都在当前元素的右侧。如果它们值小于当前值且下标大于当前下标就构成逆序对。7.2 离散化步骤如果原数组的值域很大比如 10^9不能直接开这么大的树状数组必须先离散化。离散化流程vectorint all nums; sort(all.begin(), all.end()); all.erase(unique(all.begin(), all.end()), all.end()); for (int x : nums) { x lower_bound(all.begin(), all.end(), x) - all.begin() 1; }排序去重后每个数值都有了唯一的“排名”排名范围是 1 到 mm 是不同数值的个数。7.3 完整 C 代码// 文件路径inversion.cpp #include bits/stdc.h using namespace std; int lowbit(int x) { return x -x; } long long countInversions(vectorint nums) { // 1. 离散化 vectorint all nums; sort(all.begin(), all.end()); all.erase(unique(all.begin(), all.end()), all.end()); for (int x : nums) { x lower_bound(all.begin(), all.end(), x) - all.begin() 1; } int m all.size(); vectorint tree(m 1, 0); auto add [](int idx, int delta) { while (idx m) { tree[idx] delta; idx lowbit(idx); } }; auto query [](int idx) { int res 0; while (idx 0) { res tree[idx]; idx - lowbit(idx); } return res; }; long long ans 0; for (int i nums.size() - 1; i 0; --i) { ans query(nums[i] - 1); add(nums[i], 1); } return ans; } int main() { vectorint nums {5, 3, 2, 4, 1}; cout countInversions(nums) endl; return 0; }7.4 运行结果说明数组 [5, 3, 2, 4, 1] 中的逆序对包括(5,3) (5,2) (5,4) (5,1) (3,2) (3,1) (2,1) (4,1)共 8 对程序输出为 8。可以通过手算验证。7.5 为什么这种方法不会超时每个元素在从右往左扫描时只执行一次query和一次add两者都是 O(log m)所以总复杂度是 O(n log n)。这个复杂度对于 n 10^5 甚至 n 10^6 的题目都能在合理时间内完成。8. 进阶实战树状数组上二分找第 k 小8.1 问题描述与思路有一类问题需要动态维护一个集合并支持查询当前集合中第 k 小的元素。如果集合中元素的值域不大可以用树状数组维护每个值的出现次数然后通过“树状数组上二分”快速定位第 k 小。这里的核心思想是二进制倍增从高位开始尝试跳跃如果当前跳到的节点值小于 k说明第 k 小在更后面于是跳过去并减去该节点值否则不跳。前提条件树状数组维护的是非负频次且所有更新都是非负操作。8.2 完整 C 代码// 文件路径kth.cpp #include bits/stdc.h using namespace std; class FenwickTree { private: vectorint tree; int n; int lowbit(int x) { return x -x; } public: FenwickTree(int size) : n(size) { tree.resize(n 1, 0); } void add(int idx, int delta) { while (idx n) { tree[idx] delta; idx lowbit(idx); } } int query(int idx) { int res 0; while (idx 0) { res tree[idx]; idx - lowbit(idx); } return res; } // 找到前缀和 k 的最小下标 int kth(int k) { int idx 0; int maxPow 1; while (maxPow 1 n) { maxPow 1; } for (int step maxPow; step 0; step 1) { int next idx step; if (next n tree[next] k) { idx next; k - tree[next]; } } return idx 1; } }; int main() { FenwickTree bit(8); vectorint nums {1, 1, 2, 2, 3, 4, 4, 4}; for (int x : nums) { bit.add(x, 1); } cout bit.kth(1) endl; cout bit.kth(3) endl; cout bit.kth(8) endl; return 0; }8.3 运行结果与解释输出1 2 4解释第 1 小元素是 1对应下标 1。第 3 小元素频次累积到 3 时已经包含了两个 1 和一个 2所以答案是 2。第 8 小元素所有数都累加完最后一个是 4。8.4 倍增时为什么从最高位 2 的幂开始树状数组的节点 c[i] 天然覆盖长度为lowbit(i)的区间。如果我们用倍增的方式构建“跳跃路径”每个 step 都是 2 的幂恰好对应树状数组某个层级上的区间长度。这样能保证每次跳跃后idx step不会跳到重复覆盖的区域从而正确累加频次。这种操作同样只要 O(log n) 次因为 step 从最大 2 的幂逐次减半到 1。9. 常见问题与排查思路9.1 树状数组的常见错误问题现象常见原因解决思路修改一个数后查询全部错误下标从 0 开始导致 lowbit 计算异常或死循环统一改为下标从 1 开始更新时数组越界add的终止条件写成idx n改为idx n查询时漏掉一部分区间query的写法用了idx lowbit(idx)查询方向应该用-不要和更新搞混逆序对答案偏大或偏小离散化时没有从 1 开始映射lower_bound后要1大数据下答案溢出逆序对数量超过了 int 范围使用long long树状数组上二分结果不对树状数组维护的不是频次或者元素可能为负确认前缀和单调不减或改用其他数据结构9.2 排查建议在调试树状数组题目时建议先写一个非常小的数组比如 n 8手动模拟一遍更新和查询的节点路径然后与程序输出对比。树状数组的问题通常集中在“方向写反”和“边界写错”这两类只要把这两点排查清楚大部分问题都能解决。另外可以在本地用暴力前缀和做对拍for (int i 1; i n; i) { int sum 0; for (int j 1; j i; j) sum a[j]; assert(sum bit.query(i)); }一旦发现不一致用二分定位出错位置效率会高很多。10. 最佳实践与工程建议10.1 封装成结构体或类尽量不要把树状数组的数组和操作散落在主函数里。封装成FenwickTree结构体或类之后多个测试用例之间创建新的对象即可不会互相污染数据。在 C 中建议将tree作为私有成员外部只能通过add和query操作。10.2 全局数组和局部数组的选择在算法竞赛中为了效率很多人会直接用全局数组。但在工程实践中更推荐封装。两者的权衡在于全局数组速度快写起来简单但多组测试时容易忘记清空。封装对象代码清晰不易出错代价是少量函数调用开销。对于绝大多数题目封装对象不会导致性能问题。10.3 时间复杂度要心里有数树状数组的 O(log n) 非常稳定但要注意常数。每次add和query的循环次数并不是 log2(n)而是更接近“二进制中 1 的个数”。当 n 10^5 时单次操作通常不到 20 次循环这是它比线段树更快的原因之一。10.4 结合差分的扩展用法树状数组不只支持单点更新、区间查询。如果配合差分数组可以实现区间更新、单点查询甚至区间更新、区间查询。后者需要维护两个树状数组但核心原理仍然不变。建议在掌握基础模板后把差分的扩展用法也练习一遍这样能把树状数组用到更多题目场景中。10.5 一个很实用的建议学习树状数组时不要只背模板一定要自己手动模拟一次 8 或 16 的完整二进制路径。把下面这张表亲手算一遍i 1, lowbit 1 i 2, lowbit 2 i 3, lowbit 1 i 4, lowbit 4 i 5, lowbit 1 i 6, lowbit 2 i 7, lowbit 1 i 8, lowbit 8然后再模拟add(3, delta)和query(7)的节点路径。这个过程只需要十分钟但理解深度远超看十篇文章。很多后来写线段树、Splay 平衡树、可持久化线段树的同学都是从树状数组的这套二进制分解中获得了对“区间划分”的直觉。希望这篇文章也能帮你打通这一层。如果觉得有用可以收藏备用写题的时候拿出来对照。