第一次接触树状数组Binary Indexed Tree也叫 Fenwick Tree时很多人都会经历一个很典型的阶段模板能背下来题目也能 AC但心里总觉得有个地方没通。背下来的代码大概是这个样子的int lowbit(int x) { return x (-x); } void add(int i, int v) { for (; i n; i lowbit(i)) { tree[i] v; } } int prefixSum(int i) { int res 0; for (; i 0; i - lowbit(i)) { res tree[i]; } return res; }写更新时i不断增大所以叫“向上”写查询时i不断减小所以叫“向下”。很多人会卡在这里为什么一个是加 lowbit一个是减 lowbit这个看起来不对称的设计为什么能保证两端都是 O(log n)如果只是应付比赛或考试背模板确实够用。但一旦遇到区间修改、树状数组二分、逆序对、离散化这些变体或者调试时发现答案总是差一点你会发现背诵不能解决结构性问题。这篇文章就把“为什么”这一层拆开讲清楚重点解决两个问题更新为什么向上查询为什么向下以及它们的复杂度为什么都是 O(log n)。1. 先纠正一个常见的理解误区这棵树不是一棵“真树”树状数组名字里带“树”但它和线段树、平衡树那类带指针、带左孩子右孩子的树并不一样。它没有真正的节点对象没有递归建树也没有孩子指针。整个结构就是一块普普通通的一维数组tree。那“树”在哪里在索引之间的跳跃关系上。tree[i]虽然不知道自己的“孩子”是谁但它知道自己在索引上覆盖哪一段区间。这个区间完全由i的 lowbit 决定tree[i]存储的是闭区间[i - lowbit(i) 1, i]上的聚合值。这是理解整个树状数组最关键的一句话。下面用n 16的几个索引来验证索引 i二进制lowbit(i)tree[i] 覆盖区间1000011[1, 1]2000102[1, 2]3000111[3, 3]4001004[1, 4]5001011[5, 5]6001102[5, 6]7001111[7, 7]8010008[1, 8]9010011[9, 9]10010102[9, 10]11010111[11, 11]12011004[9, 12]13011011[13, 13]14011102[13, 14]15011111[15, 15]161000016[1, 16]1.1 为什么恰好覆盖这么一段观察二进制规律你会发现 lowbit 的本质是去掉二进制编号最右侧的 1 后面的所有 0也就是取出最右侧那个 1 所代表的权值。6 110最右侧 1 的权值是10也就是 2所以lowbit(6) 2。12 1100最右侧 1 的权值是100也就是 4所以lowbit(12) 4。8 1000最右侧 1 的权值就是1000也就是 8所以lowbit(8) 8。一个很容易记住的结论是如果lowbit(i) k那么tree[i]就负责[i - k 1, i]这一段。也就是说tree[i]的职责范围长度恰好等于lowbit(i)。很多初学者拿到树状数组结构图时会直接用线段树那套理解方式去解读叶子节点存原数组内部节点存区间和。但在树状数组里并没有一棵“显式”的树结构在维护你。你看到的图其实是低层逻辑关系到底谁是tree[i]的父节点、谁是它的子节点完全是由lowbit算出来的。1.2 为什么不是“完整二叉树”线段树里每个节点负责的区间是固定的对半拆分左孩子右孩子也明确树状数组则完全不同。它负责的区间长度不是靠“均分”来的而是靠二进制低位拆出来的。说白了树状数组是“按二进制权值分块”的数据结构。每个下标 i 能管多长取决于 i 本身二进制长什么样。这种设计在构建时不需要递归运行时不传参找儿子甚至在空间上就是原数组大小 n而线段树通常要开 4 倍空间。它不是一棵“真树”却用数组索引之间的位运算把树形依赖表达得干干净净。这也是为什么理解 lowbit 比背代码重要你只有知道tree[i]管的是哪一段才能理解后面更新和查询为什么是那样跳的。2. lowbit为什么它是整个数据结构的算术根基2.1 一行代码二进制的分水岭lowbit 的常见写法是x (-x)。在大多数编程语言里负数用的是补码表示。补码的意思是-x (~x) 1。x (-x)的效果是保留 x 二进制中最右侧的 1其余位全部归零。举几个例子x 12 1100 -x -12 0100 补码形式只关注取最低位 1 之后的位 lowbit(12) 0100 4 x 10 1010 lowbit(10) 0010 2 x 7 0111 lowbit(7) 0001 1有的读者可能会疑惑为什么lowbit(12)不是 8 也不是 2因为 12 的二进制是1100最右侧的 1 在第三位代表 2³也就是 4。它左边的 1 更高右边的位全是 0。所以保留“最低位的 1”这个操作在二进制世界里就是抠出一个“权值”。2.2 lowbit 本质上是“最小分块单位”如果从功能角度看lowbit 承担了两件事。第一它是tree[i]管辖区间长度的度量。tree[i]负责[i - lowbit(i) 1, i]而这段长度就是lowbit(i)。第二它决定了索引跳跃的步长。更新与查询的两条路径都是以 lowbit 为台阶往上或往下走。为什么不选一个固定的块大小比如 2 或 4因为固定块大小无法同时满足“查询前缀和”和“单点更新”两个需求。你想要单点更新时快速影响所有相关区域又想要区间查询时快速合并结果。lowbit 让区间长度与下标二进制绑定这样每个索引都能高效跳出二进制的 1 位链。打个比方lowbit 像是给你一套按 1、2、4、8、16 划分大小的拼图。每次合并或拆散只需要处理这些“标准件”。标准件数量不超过 2 的幂次所以单次查询或更新的跳跃次数自然就被压在了二进制位数级别。3. 更新向上走i lowbit(i) 到底在维护什么现在进入核心问题为什么更新时i要加 lowbit。假设原数组是a[1..n]要做单点更新a[3] v。a[3]在哪些tree节点里出现过根据tree[j]覆盖区间[j - lowbit(j) 1, j]我们只需要找到所有覆盖位置 3 的 j。手动枚举几个j 3覆盖[3, 3]包含 3。j 4覆盖[1, 4]包含 3。j 8覆盖[1, 8]包含 3。j 16覆盖[1, 16]包含 3。你会发现这一串是3 → 4 → 8 → 16。而从 3 开始加 lowbiti 3lowbit(3) 1加完得 4。i 4lowbit(4) 4加完得 8。i 8lowbit(8) 8加完得 16。恰好就是那条路径。3.1 为什么祖先一定是“加 lowbit”而不是别的因为tree[j]覆盖区间的右端点是j左端点是j - lowbit(j) 1。如果区间覆盖了一个点i那么这个区间的右端点j必须满足j - lowbit(j) 1 i j你可以验证所有满足这个条件的j都会在i不断执行j i lowbit(i)的过程中出现。也就是说覆盖i的所有tree节点会顺着“从当前位置向右上方跳”的链路一个个被找到。从二进制角度看也直观3 011它的 lowbit 是001加完跳成4 100。4 100它的 lowbit 是100加完跳成8 1000。8 1000lowbit 是1000加完跳成16 10000。每次更新都会把最低位的 1 往更高位推进。3.2 这棵树上的“父节点”为什么不走右孩子很多学线段树的人会习惯性想更新的阶段应该先更新自己再更新父节点、祖父节点。树状数组也是这个逻辑只不过它的父节点不是通过i / 2找到的而是通过i lowbit(i)找到的。那为什么不是i 1或i 1这种简单关系原因很简单树状数组的父节点必须负责一个更大的、且包含当前区间的二进制分块区间。这个分块区间的大小和位置由父节点二进制的最低位 1 决定。按位运算保证了这种“包含又错开”的结构稳定成立。3.3 更新复杂度为什么是 O(log n)从i出发每次i lowbit(i)之后i的二进制最低位 1 的位置至少左移一位。比如3 的 lowbit 是 1加完变成 4最低位 1 从第 0 位跳到第 2 位。4 的 lowbit 是 4加完变成 8最低位 1 从第 2 位跳到第 3 位。8 的 lowbit 是 8加完变成 16最低位 1 从第 3 位跳到第 4 位。对于n以内的数字二进制位数最多是⌊log₂ n⌋ 1。既然最低位 1 的位置只会不断提高那它最多提高⌊log₂ n⌋次就会被推出n的范围。所以更新的循环次数是 O(log n)。这里要注意复杂度上限是“二进制位数级别”而不是“数字大小级别”。一个 10 万以内的数字二进制位只有 17 位左右所以循环次数最多十几二十次。这也解释了为什么树状数组在n 1e5、1e6量级时跑得飞快。4. 查询向下走i - lowbit(i) 是如何拼出前缀和的更新是往右上方跳查询却是往左下方跳。先看一个具体例子。求前 13 项前缀和prefixSum(13)。从i 13开始i 13lowbit(13) 1累加tree[13]它覆盖[13, 13]。i 13 - 1 12lowbit(12) 4累加tree[12]它覆盖[9, 12]。i 12 - 4 8lowbit(8) 8累加tree[8]它覆盖[1, 8]。i 8 - 8 0循环结束。拼起来是[1, 13] [1, 8] ∪ [9, 12] ∪ [13, 13]完美覆盖既不重叠也不遗漏。如果用区间求和sum(l, r)就变成prefixSum(r) - prefixSum(l - 1)。这也是为什么树状数组只能做前缀和查询区间和只是两个前缀和相减。4.1 为什么拆出来的区间一定是“二进制块”从二进制看 1313 1101查询时每一步都减去当前数字最低位的 11101 - 1000 减去 0101? 不对稍微换个角度更清楚更准确的表达是13 1101 第一步最低位 1 的权值是 1所以取 [13, 13] 剩下1100 12 第二步12 的最低 1 权值是 4所以取 [9, 12] 剩下1000 8 第三步8 的最低 1 权值是 8所以取 [1, 8] 剩下0所以前缀和查询的本质是把一个前缀区间拆成若干个“长度为 2 的幂”的区间拼接起来。二进制中有多少个 1就会拆出多少个块。而二进制中 1 的个数不会超过⌊log₂ n⌋ 1。4.2 为什么查询是“向下”而不是“向上”因为我们要的是从 1 到 i 的前缀和而不是单点 i 所在的所有覆盖区间。更新是为了告诉所有覆盖当前点的节点“这个点的值变了”所以必须一路向上找父节点父节点才会同步。查询是为了把[1, i]拆成已知的、不重叠的tree节点所以必须一路向下释放已经算好的小区间。每次减掉 lowbit其实是把当前区间中最右侧的那一块交给答案。把这两个逻辑放在一起看你会得到一条清晰主线更新时你要修改的是“影响我的节点”。查询时你要加起来的是“组成我的片段”。“影响我的节点”在结构图中位于当前节点上方所以向上 “组成我的片段”在当前节点左侧或把自己本身拆出去所以向下。它们不是同一个方向也不应该相同。4.3 查询复杂度为什么是 O(log n)查询过程中每做一次i - lowbit(i)二进制里至少会有一个 1 变成 0。i 13的二进制是1101经历了三步1101 1100 1000 0000三次都是把最低位的 1 消掉。任意一个不超过 n 的数字二进制中最多有⌊log₂ n⌋ 1个 1。所以循环次数最多是“二进制中 1 的个数”必然也是 O(log n)。值得注意的是查询的实际速度还取决于 i 的二进制中 1 的密集程度。比如 i7 二进制是 111查询就要循环 3 次i8 二进制是 1000查询只要循环 1 次。这比复杂度上限还快很多情况下平均表现比线段树更轻量。5. 复杂度证明为什么两端都是 O(log n)这一段专门做一个更形式化的总结因为初学者最容易卡在这里更新和查询的方向不同凭什么恰好都是 O(log n)操作跳法每个循环里发生什么循环次数的最直观约束次数级别单点更新i lowbit(i)最低位 1 的位置左移位数上限O(log n)前缀查询i - lowbit(i)二进制中某个 1 被清零二进制中 1 的个数O(log n)5.1 更新最低位 1 的位置严格递增设当前数字为 i二进制表示为...???100...0其中最低位 1 后面有 k 个 0。那么lowbit(i) 2^k i lowbit(i) ...???100...0 100...0低 k 位变成 0第 k 位原本的 1 会参与进位结果至少会影响到第 k 位或更高位。进位的效果是让“最低位 1”的位置移动到更高位置。因为 i 始终不超过 n而 n 的二进制位只有⌊log₂ n⌋ 1位所以“最低位 1 的位置”最多只能上升这么多次。这就是更新循环次数 O(log n) 的严格理由。5.2 查询二进制 1 的总数严格递减设当前数字为 i最低位 1 的权值为 lowbit(i)。执行后i i - lowbit(i)因为最低位 1 变 0而它右侧本来就全是 0所以这一次减法至少让二进制中 1 的个数减少 1。最坏情况下i 的二进制全是 1例如i 2^k - 1它有 k 个 1因此循环 k 次。k 仍然是⌊log₂ n⌋级别。这就是查询循环次数 O(log n) 的严格理由。5.3 为什么树状数组不是 O(1)有人可能会问既然每次查询都可能只循环几次为什么还要说 O(log n) 而不是 O(1)因为复杂度描述的是最坏情况。n 很大的时候比如 n2³⁰一个二进制全 1 的数字查询确实要循环 30 次。但 30 次对一次查询来说非常快这也是树状数组在工程和竞赛里能大量使用的原因之一。还有一个容易忽略的点树状数组的单次操作循环次数不是由 n 的线性规模决定而是由 n 的二进制长度决定。n 1e6和n 1e9在二进制长度上只差 10 位左右所以它的扩展性比普通数组维护方法好很多。5.4 和线段树对比一下线段树每次操作的复杂度也是 O(log n)但它是通过递归二分树高得到的。树状数组则是通过“二进制分块跳链”得到的。两者复杂度同级但树状数组更省空间、代码更短、常数更小。代价是它表达能力有限不适合处理最大值、最小值这类不满足“可减性”的聚合信息。对比维度树状数组线段树空间复杂度O(n)O(4n)单次操作复杂度O(log n)O(log n)代码量很短较长是否支持区间最大值难支持是否支持区间赋值麻烦容易常数小较大如果你的问题只是“单点更新 区间求和”树状数组是首选。6. 从板子到工程三个最容易踩的坑和一条排查链路树状数组代码短但上手并不代表不会错。实际写题或做项目时下面几个坑出现频率极高。6.1 下标从 0 开始树状数组的下标几乎必须从 1 开始。原因很简单lowbit(0) 0如果你在 i0 时调用更新或查询i lowbit(i)会变成i 0死循环。处理办法有两种读入数据时把索引整体 1。用idx 1作为树状数组里的实际位置。如果不一致前缀和会整个错位。6.2 把单点更新当成赋值add(i, v)的本意是在原数组第 i 个位置加上一个值 v不是把原数组第 i 个位置改成 v。如果你把一个数改成另一个数需要先计算差值再用差值调用 add。例如把a[i]从旧值 oldV 改成 newVint delta newV - oldV; add(i, delta); oldV newV;如果你直接add(i, newV)那么更新之后的值是原值加 newV而不是 newV。这种错误在小规模数据上不太容易发现因为样例经常只有几次更新不容易累积。6.3 离散化之后忘记对应关系树状数组经常和离散化一起出现尤其是在逆序对问题里。离散化的本质是把值域压缩成 1..m 之间的连续整数然后把这个整数作为树状数组下标。这里最容易出现的错误是离散化结果从 0 开始忘了 1。排序后去重但在查询时仍然用原数组去比较。数值相等但没有正确处理“等于”的情况导致统计逆序对时多算或少算。建议是先在一个小例子上手动模拟一遍离散化结果再写树状数组部分。6.4 一条顺向排查链路如果结果不对不要一上来就打印整棵 tree。按下面顺序排查检查下标是否从 1 开始。检查树状数组初始化如果初始数组不是全 0需要逐个 add而不是直接给 tree 赋值。手动模拟某次 add选定一个小索引比如 i3手动算出 3、4、8、16 这条更新链检查代码是否访问了这些位置。手动模拟某次查询选定一个 i比如 i13手动拆出 [13,13]、[9,12]、[1,8]再用手算前缀和验证。检查更新次数和数据范围n 是否超出 tree 数组大小是否中间结果已经超过 int 范围。排查时最好先用 n8 或 n16 的小数据。小数据能手工列出每个 tree[i] 覆盖区间也最容易暴露 lowbit 方向写反的问题。这套排查顺序的核心思路是先确认数据组织方式再确认单次操作路径最后确认整体累加结果。不要一开始就去调整 lowbit 的实现也不要把所有错误都归因于位数不对。7. 树状数组的真正价值不只是前缀和还可以上溯和二分如果只是单点加、区间求和树状数组的定位还比较窄。但当你理解了 lowbit 跳链之后会发现它能扩展出一系列很自然的变体。7.1 逆序对统计逻辑建立在“可加性”上逆序对问题的经典做法是对原数组离散化。从前往后扫描每遇到一个数 a[i]就在树状数组下标为 rank(a[i]) 的位置加 1。在加之前或之后用前缀和查询已经出现过的、比当前数大的数字个数。如果从前往后扫统计“已出现过且比当前数大”的数量就是i - 1 - prefixSum(rank)如果更偏好减掉左侧比当前数小的可以用prefixSum(n) - prefixSum(rank)。这背后的逻辑是树状数组维护的是权值的频次分布。单点更新是更新某个权值的出现次数前缀查询是统计某个值域范围内的已经出现次数。lowbit 的查询链正好把频次区间拆成连续的不相交块所以统计复杂度也是 O(log n)。7.2 树状数组二分找第 k 小树状数组一个很有意思的高级用法是在它上面做二分查找找“前缀和达到某个阈值的最小下标”。原理是树状数组的 tree[i] 是“按 2 的幂分块”的所以我们可以从高到低尝试每个二进制位跳跃式地构造答案。// 找到最小的 pos使得 prefixSum(pos) k // 需要 tree 中存的值都是非负的 int kth(int k) { int pos 0; int maxPow 1; while ((maxPow 1) n) { maxPow 1; } for (int step maxPow; step 0; step 1) { int nextPos pos step; if (nextPos n tree[nextPos] k) { k - tree[nextPos]; pos nextPos; } } return pos 1; }这段代码看起来和普通二分不同但它本质上是在枚举答案的二进制位。每次尝试加入一个 step 时tree[pos step]恰好覆盖了一个连续的块。如果tree[pos step]小于剩余 k说明答案在更右边把 k 减掉这块的值再继续尝试更小的 step。这个技巧之所以能成立正是因为在树状数组里tree[i]覆盖的区间长度就是lowbit(i)而枚举 step 的过程中pos step的组合可以构造出“从左往右跨过若干个连续块”的效果。利用这个能力可以避免在树状数组外面再套一次二分从而把“单次找第 k 小”从 O(log² n) 降成 O(log n)。7.3 区间修改 区间查询两个树状数组常规树状数组是单点更新、前缀查询。要做区间修改和区间查询可以用差分数组。设差分数组 d[i] a[i] - a[i-1]那么区间 [l, r] 加 v变成d[l] v、d[r1] - v。前缀和sum(1..x)可以展开成(x 1) * Σd[i] - Σ(i * d[i])所以用两个树状数组bit1[i] 维护 d[i]; bit2[i] 维护 i * d[i];区间修改就更新两次区间查询就用两个前缀和组合long long prefixSum(int x) { return (x 1) * sum(bit1, x) - sum(bit2, x); } long long rangeSum(int l, int r) { return prefixSum(r) - prefixSum(l - 1); }这个变体看起来复杂但核心没有变更新时仍然一路向上加查询时仍然一路向下减。lowbit 的跳链机制完全没有改变。7.4 为什么这些变体都能复用同一套跳链因为所有变体都建立在同一个前提上任意前缀 [1, x] 都可以被若干棵“以 lowbit 划分的区间块”无损拆解。只要你维护的信息满足“可加性”并且能通过“一加一减”得到目标区间信息树状数组这套跳链就适用。它之所以能从小小的前缀和扩展到二维偏序、区间修改、第 k 小问题正是因为 lowbit 把二进制分块的抽象能力固化了下来。当然也要注意边界如果维护的信息不满足“可减性”比如最大值、最小值树状数组很难直接支持区间查询。这时更推荐线段树。如果操作是“区间赋值”而不是“区间加”并且还要求快速查询树状数组处理起来很别扭线段树带 lazy 标记会更自然。如果值域不是 1..n通常需要离散化不能直接拿原始大数值当下标。8. 收束理解 lowbit才算是真正拥有树状数组回到最开始的问题。更新时向上跳是因为一个位置的值发生变化所有覆盖它的上层区间块都要同步更新查询时向下跳是因为一个前缀和要拆成若干个二进制分块才能不重不漏地加出答案。两条路径方向相反但都基于同一个 lowbit。更新跳的是“父链”查询消的是“分块链”。前者受位数的限制后者受二进制中 1 的个数限制。无论从哪一端看都落在 O(log n) 上。这其实是一个值得记住的思维框架遇到树状数组先问tree[i]管的是哪段区间再问更新一个点哪些 tree 节点要变答沿i lowbit(i)向上。最后问查询一个前缀我要拆哪些块答沿i - lowbit(i)向下。如果哪天你忘了树状数组代码只需要花十秒钟推一下tree[i]的覆盖范围和 lowbit 公式模板就能自己重新长出来。真正有价值的东西从来不是那几行代码而是代码背后那条由二进制位控制的跳链。理解它之后树状数组就不再是一个要背的模板而是一个可以信任、可以扩展、可以自己调试的数据结构基础。