树状数组Binary Indexed Tree又称 Fenwick Tree是一种轻量级的区间数据结构常用于单点更新和前缀和查询。它能把一次更新或一次查询从 O(n) 降到 O(log n)而且代码量只有十来行非常适合在算法题、实时排行榜、逆序对统计、动态第 K 小等场景中使用。很多初学者记住i i -i和i - i -i两个式子却不明白它们背后的二进制语义导致遇到区间修改、离散化、树状数组上二分时又容易写错。这篇文章从二进制索引的原理讲起先带你跑通基础单点更新和前缀查询再逐步扩展到逆序对、离散化、树状数组上的二分最后给出常见错误排查路径和工程化建议。学完后你能独立实现树状数组的常见应用也能在遇到下标越界、查询结果不符、更新不生效等问题时快速定位根因。1. 理解树状数组从区间求和到二进制索引1.1 为什么需要树状数组先看一个经典问题。给定一个长度为 n 的整数数组 a需要支持两种操作单点更新把 a[i] 的值增加 delta。前缀查询求 a[1] a[2] ... a[i] 的和。如果直接用普通数组单点更新很快O(1) 就能完成但前缀查询需要循环相加最坏是 O(n)。如果预处理前缀和数组 prefix[i]前缀查询可以做到 O(1)但单点更新后需要重新计算受影响的所有前缀和最坏也是 O(n)。当 n 很大、操作次数很多时这两种做法都无法接受。线段树也能解决这个问题它能把单点更新和区间查询都做到 O(log n)。但线段树的实现需要建树、递归或者使用数组模拟二叉树结构更重代码更长常数因子也更大。树状数组正是针对“单点更新 前缀查询”这类问题设计的轻量级结构。它同样能实现 O(log n) 的更新和查询但空间占用只有 O(n)代码结构非常紧凑。树状数组的适用范围比线段树窄一些但它覆盖了算法题里相当多的需求前缀和、逆序对、区间和、动态第 K 小、差分维护区间修改等。理解树状数组的价值不只是背模板更是理解它如何利用整数二进制的位数来组织信息。1.2 核心思想二进制索引与 lowbit树状数组的底层依赖一个关键函数 lowbit。对于正整数 xlowbit(x)表示 x 的二进制表示中最低位的 1 所对应的值。例如x 6二进制是 110最低位的 1 在第二位对应值 2所以 lowbit(6) 2。x 8二进制是 1000最低位的 1 在最高位对应值 8所以 lowbit(8) 8。x 3二进制是 11最低位的 1 对应值 1所以 lowbit(3) 1。计算 lowbit 的常用公式是x -x。这是因为负整数在计算机中使用补码表示-x等于把 x 按位取反再加 1这样x -x恰好能保留 x 最低位的 1。树状数组用一个额外数组 c 来保存某些区间和。下标从 1 开始c[i] 保存的是原数组中区间 [i - lowbit(i) 1, i] 的和。也就是说c[i] 所覆盖的区间长度恰好是 lowbit(i)。看一个 n 8 的例子下标 ilowbit(i)c[i] 覆盖的原数组区间11[1, 1]22[1, 2]31[3, 3]44[1, 4]51[5, 5]62[5, 6]71[7, 7]88[1, 8]从这张表可以看出树状数组并不是一颗严格意义上的二叉树而是一棵基于二进制的“索引树”。更新某个位置时需要向上合并到所有包含该位置的 c[j]查询前缀和时则沿着区间边界向左累加。这个过程中下标变化完全由 lowbit 决定。理解交换律更新操作i lowbit(i)是从当前节点跳到它上层的覆盖区间查询操作i - lowbit(i)是从当前节点跳到左侧相邻区间。这个方向相反的设计正是树状数组能在 log n 级别完成操作的原因。1.3 树状数组、前缀和数组与线段树的对比在设计方案时需要知道树状数组的边界。下面表格对比三种常见做法方案单点更新复杂度前缀查询复杂度区间查询复杂度实现难度适用场景普通数组O(1)O(n)O(n)极低几乎不更新只做全量扫描前缀和数组O(n)O(1)O(1)极低更新很少查询非常频繁线段树O(log n)O(log n)O(log n)较高复杂区间问题如区间最值、懒标记树状数组O(log n)O(log n)O(log n)低单点更新 前缀/区间和场景树状数组最大的特点是用极简代码换来了接近线段树的效率。它不是万能的例如要求区间最大值、区间最小值时树状数组处理起来会更麻烦因为最值不满足加法可逆性。但在“和”这个语义下树状数组往往是最优先考虑的备选结构。2. 树状数组的代码骨架单点更新与前缀查询2.1 环境与语言选型下面示例使用 C 和 Python 两种语言核心逻辑完全一致。C 版本更适合算法竞赛Python 版本更适合快速验证思路。无论使用哪种语言树状数组的下标都必须从 1 开始否则 lowbit 和更新路径会出错。如果是学习环境建议先在一个包含数组长度 n 和若干修改、查询操作的本地文件中调试。如果是生产环境还需要关注数据范围、整数溢出、并发访问等额外问题。下面先给出最小可运行的模板。2.2 基础数组结构定义树状数组只需要一个一维数组tree长度至少为 n 1下标 1 到 n。初始化时所有元素为 0。原数组可以不保留直接通过 add 操作把每个元素加入树中。#include bits/stdc.h using namespace std; const int MAXN 100005; int tree[MAXN]; int n; inline int lowbit(int x) { return x -x; } void add(int idx, int delta) { while (idx n) { tree[idx] delta; idx lowbit(idx); } } int prefixSum(int idx) { int sum 0; while (idx 0) { sum tree[idx]; idx - lowbit(idx); } return sum; } int rangeSum(int l, int r) { return prefixSum(r) - prefixSum(l - 1); }Python 版本使用列表数组长度需要 n 1实际使用的是下标 1 到 n。class Fenwick: 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 prefix_sum(self, idx): ans 0 while idx 0: ans self.tree[idx] idx - self.lowbit(idx) return ans def range_sum(self, l, r): return self.prefix_sum(r) - self.prefix_sum(l - 1)2.3 add 操作自底向上更新add(idx, delta)的作用是把原数组下标 idx 的位置增加 delta并同步更新所有覆盖这个位置的树状数组节点。由于 c[i] 覆盖的是[i - lowbit(i) 1, i]所以如果一个节点 j 覆盖了 idx那么必须存在某个路径能从 idx 一步步走到 j。这个路径就是不断执行idx lowbit(idx)。以 n 8、更新 idx 3 为例初始 idx 3lowbit(3) 1更新 tree[3]。idx 4lowbit(4) 4更新 tree[4]。idx 8lowbit(8) 8更新 tree[8]。idx 16超过 n结束。可以看到更新位置 3 时覆盖该位置的下标是 3、4、8。这些下标正好对应二进制 0011 - 0100 - 1000 的进位方向。这就是为什么树状数组又叫二进制索引树。2.4 query 操作自顶向下累加prefixSum(idx)求的是原数组 [1, idx] 的和。它的拆解过程是从当前 idx 开始把 tree[idx] 累加到答案然后让 idx 跳到下一个未覆盖的左侧区间直到 idx 变成 0。以查询前缀和到下标 7 为例idx 7lowbit(7) 1累加 tree[7]对应区间 [7, 7]。idx 6lowbit(6) 2累加 tree[6]对应区间 [5, 6]。idx 4lowbit(4) 4累加 tree[4]对应区间 [1, 4]。idx 0结束。累加的结果就是 [1, 4] [5, 6] [7, 7] [1, 7]。7 的二进制是 0111查询过程中下标依次变成 0110、0100、0000每次减去最低位的 1。所以查询的本质是剥离二进制最低位的 1而更新则是不断向最高位进位。两个操作正好互补。2.5 区间和查询因为前缀和可以写成 prefixSum(r) - prefixSum(l - 1)树状数组可以轻松支持区间查询。这里要注意 l 的下界是 1不能传 0否则 prefixSum(0) 会在循环中直接返回 0但 l - 1 0 没有问题。实际区间查询时如果 l 可能为 1计算prefixSum(l - 1)时传的就是 0函数内 while 不执行直接返回 0结果是正确的。写一个简单的验证过程int a[] {0, 1, 2, 3, 4, 5}; // 下标从 1 开始a[1]1, a[2]2, a[3]3, a[4]4, a[5]5 n 5; memset(tree, 0, sizeof(tree)); for (int i 1; i n; i) { add(i, a[i]); } printf(%d\n, rangeSum(2, 4)); // 2 3 4 9验证时不仅要看输出结果是否等于 9还可以手动模拟 add 后的 tree 数组确认每一步累加区间是否正确。如果结果偏大或偏小优先检查下标是否从 1 开始、数组是否越界、以及 lowbit 是否写成了x (x - 1)这个表达求的是移除最低位 1 之后的值不是 lowbit。3. 树状数组的常见应用逆序对与计数场景3.1 用权值树状数组求逆序对逆序对定义数组 a 中如果 i j 且 a[i] a[j]则 (i, j) 是一个逆序对。朴素做法是双重循环时间复杂度 O(n^2)。使用树状数组时思路是把“值”当作下标构建权值树状数组统计每个值出现的次数。一种常用遍历方式是从右往左扫描原始数组。对于当前元素 a[i]需要知道在它右边已经出现过的元素中有多少个比它小。这正好等于当前权值树状数组中下标 [1, a[i] - 1] 的累计次数。统计完这个数量后再把 a[i] 的出现次数加 1。例如数组[3, 1, 2]从右往左先处理 2统计比 2 小的数当前没有ans 0然后 add(2, 1)。处理 1统计比 1 小的数当前没有ans 0然后 add(1, 1)。处理 3统计比 3 小的数当前已经出现了 1 和 2共 2 个所以 ans 2。最后 ans 2对应的逆序对是 (3,1) 和 (3,2)正确。这里的关键是权值树状数组的下标范围由值域决定。如果 a[i] 的范围很大比如达到 1e9就不能直接开这么大的数组必须先离散化。3.2 离散化处理大数值离散化的本质是把原始数值映射到连续的小范围下标。由于我们只关心数值之间的大小关系所以可以排序后去重再把每个数映射为它在有序数组中的排名。vectorint v(a.begin(), a.end()); sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); for (int i 0; i n; i) { int rank lower_bound(v.begin(), v.end(), a[i]) - v.begin() 1; // 使用 rank 作为权值树状数组的下标 }如果数组里有重复值所有相同的值会映射到同一个 rank因此在统计逆序对时从右往左遍历需要先查询再更新。如果先更新再查询会把等于当前值的元素也计入“比当前值小”的数量导致错误。离散化后的树状数组大小只需要等于去重后的元素个数 m不需要关心原始值域。下面给出完整 C 逆序对代码long long inversionCount(vectorint a) { vectorint v a; sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); int m v.size(); Fenwick bit(m); // 自行实现n m long long ans 0; for (int i a.size() - 1; i 0; i--) { int rank lower_bound(v.begin(), v.end(), a[i]) - v.begin() 1; ans bit.prefix_sum(rank - 1); bit.add(rank, 1); } return ans; }注意 ans 要用 long long因为逆序对数量最大可能是 n * (n - 1) / 2在 n 较大时超出 int 范围。3.3 逆序对v2树状数组上的二分统计在一些题解和算法视频里逆序对 v2 通常指在树状数组上使用二分查找来优化某些统计过程。例如给定一个排列要找到第 k 小的元素所在位置或者在动态插入元素的过程中维护全局第 k 小。这类问题如果只依赖普通prefix_sum需要循环查询每个位置复杂度是 O(n log n) 或更差。利用树状数组的二进制结构可以在 O(log n) 时间内完成“找到第一个前缀和大于等于 k 的下标”也就是动态集合中的第 k 小元素。这个操作并不需要额外写一个二分搜索框架而是从二进制高位到低位逐位构造答案。下一节详细说明。逆序对 v2 的一个常见场景是先通过离散化建立权值树状数组然后一边插入元素、一边用树状数组上的二分查询某个排名的位置从而在 O(n log n) 内完成逆序对统计和排名维护。这里要特别注意的是prefix_sum(i)返回的是小于等于 i 的元素个数因此第 k 小对应的位置是findKth(k)而逆序对统计需要的是当前值左侧有多少个更大的元素需要结合扫描方向灵活转换。4. 树状数组上的二分第 K 小与排名查询4.1 问题定义在动态集合中找第 K 小假设一个初始为空的可重集合支持两种操作插入一个值查询当前集合中第 k 小的元素。朴素做法是维护一个有序数组插入时找到位置并移动元素最坏 O(n)。使用优先队列只能快速得到最值无法直接回答第 k 小。使用平衡树可以实现但实现复杂。如果值域已知且不大可以用权值树状数组。第 k 小的问题可以转化为在权值树状数组上找到一个最小的下标 idx使得prefix_sum(idx) k。换句话说从左到右累加每个值出现的次数当累计次数第一次达到 k 时当前值就是第 k 小元素。4.2 二分的两种实现方式第一种方式最直观在 [1, m] 上做普通的整数二分每次用prefix_sum(mid)判断是否大于等于 k。这样单次查询复杂度是 O(log m * log m)即 O(log^2 n)。这种方式容易理解适合确认思路但在 n 很大且查询次数很多时不够高效。第二种方式利用树状数组每个节点覆盖区间的特点从最高位开始向下枚举二进制位。设pos当前构造出的答案初始为 0cnt为已累计的个数初始为 0。倒序枚举最大的二进制位2^p判断pos 2^p是否越界以及cnt tree[pos 2^p]是否小于 k。如果仍小于 k说明目标位置在右侧可以累加这一段然后让 pos 加上2^p。枚举结束后pos 1 就是第 k 小元素的下标。这个方法的本质是把普通二分替换成基于二进制位的倍增查找复杂度为 O(log n)。4.3 模板代码实现// 查找第一个前缀和 k 的下标k 至少为 1 // tree 是权值树状数组n 是值域大小 int findKth(int k) { int pos 0; // 最大的不超过 n 的 2 的幂也可以使用 log2(n) 或预处理 int maxPow 1; while (maxPow n) maxPow 1; maxPow 1; for (int step maxPow; step; step 1) { int next pos step; if (next n tree[next] k) { k - tree[next]; pos next; } } return pos 1; }这里使用的是递归式二进制拆分tree[next]保存的是区间(pos, pos step]的累计次数。如果这段区间里的总数仍然小于 k说明第 k 小在更右边的区间于是从 k 中减掉这段数量并移动 pos。对照一下维护一个支持插入和查询第 k 小的完整类可以写成struct DynamicKth { int n; vectorint tree; DynamicKth(int n) : n(n), tree(n 1, 0) {} void add(int idx, int delta) { while (idx n) { tree[idx] delta; idx idx -idx; } } int findKth(int k) { int pos 0; int maxPow 1; while (maxPow n) maxPow 1; maxPow 1; for (int step maxPow; step; step 1) { int next pos step; if (next n tree[next] k) { k - tree[next]; pos next; } } return pos 1; } };使用示例假设值域范围是 [1, 5]依次插入 3、1、3、2再查询第 3 小。树状数组中每个位置的次数分别为 [1, 1, 2, 0, 0]前缀和依次为 [1, 2, 4, 4, 4]所以第 3 小是值 3。运行findKth(3)应该返回 3。4.4 与平衡树 / 线段树上二分的对比树状数组上的二分只能处理可加且可逆的统计信息比如元素个数、和。平衡树可以同时维护排名、前驱、后继、区间翻转等更复杂信息但实现复杂度高。线段树上二分也能实现类似功能但需要存储左右子树代码更重。方案插入/删除复杂度查第K小复杂度实现工作量适用值域平衡树O(log n)O(log n)高任意线段树 二分O(log n)O(log n)中离散化后的值域树状数组 二进制倍增O(log n)O(log n)低离散化后的值域如果只做“动态集合插入 查询第 k 小”树状数组方案足够好用。如果需要删除、查找前驱后继那么树状数组也能通过计数数组配合 prefix_sum 二分完成一部分但代码会复杂一些。5. 常见问题与排查路径5.1 下标从 0 开始导致的死循环或错误树状数组的所有操作都要求下标从 1 开始。如果原数组下标从 0 开始直接使用会出错。例如add(0, delta)时因为0 -0等于 0idx 0循环永不结束程序卡死。解决方案在所有原始下标上统一加 1。如果题目给定的是下标从 1 开始就不需要改。如果是从 0 开始的数组那么在调用 add、query 时记得把传入下标转换为 1-based。5.2 lowbit 计算错误lowbit(x) x -x。有人会写成x (x - 1)这两个结果完全不同。x (x - 1)会把最低位的 1 清零得到的是移除了最低位 1 之后的值。例如 x 6x -x是 2而x (x - 1)是 4。后者会导致更新和查询路径错乱。排查方式输出几个典型值的 lowbit与预期对比。可以用这段代码检查for (int i 1; i 16; i) { cout i (i -i) endl; }期望结果是 1、2、1、4、1、2、1、8、1、2、1、4、1、2、1、16。5.3 离散化时排序去重错误离散化前必须排序并去重。如果去重后仍用原始值作为下标可能导致数组越界。另外lower_bound返回的迭代器减v.begin()得到的是从 0 开始的排名因此要加 1 才能作为树状数组下标。常见错误int rank lower_bound(v.begin(), v.end(), a[i]) - v.begin(); // 错误应为 1 bit.add(rank, 1);如果 rank 为 0add 会陷入死循环。这也解释了为什么凡是使用lower_bound求排名时都必须加 1。5.4 更新后查询结果不对先确认更新是否正确。树状数组的 add 只修改了受影响节点不修改原数组。如果你一边用a[i]直接取值一边又用 tree 查询就可能出现不一致。推荐做法是原数组只保存真实数据树状数组只负责前缀和信息。如果原始数据变化必须同步调用 add。另外如果树状数组的 add 和 query 使用了不同的 n 作为边界会导致某些操作没有覆盖到正确区间。比如 add 用 n 10query 用 n 100虽然语法不报错但语义已经不对了。5.5 整数溢出逆序对数量最大是 n*(n-1)/2n 稍大就可能超过 2^31-1。树状数组内部假设存储次数也应使用 64 位整数。C 中建议使用long long或int64_tPython 中整数没有溢出问题但要注意性能。5.6 树状数组上二分时的边界findKth函数要求 k 在 1 到当前总数之间。如果传入了大于总数的 k算法会返回 n1导致访问越界或错误结果。必须在使用前维护一个total变量记录当前元素个数并在查询前判断。下面用表格汇总排查顺序问题现象常见原因检查方式处理建议更新时程序卡死传入下标为 0检查 add 的参数是否可能为 0下标统一加 1查询前缀和结果偏小或偏大lowbit 写错输出 lowbit 序列对比使用x -x离散化后越界排名未加 1检查 rank 值在 lower_bound 结果上加 1更新后数据不一致原数组和树状数组不同步打印 tree 数组保证所有修改都走 add逆序对 ans 溢出使用 int 存储结果查看数据范围改用 long long二分返回错误位置查询前未判断 k 范围打印 total 和 k增加 total 维护和边界判断6. 树状数组的最佳实践与扩展方向6.1 使用树状数组的最佳实践清单当你决定使用树状数组时可以按下面清单检查确认操作是“单点更新 前缀查询”或可以转化为这个模型。确认下标从 1 开始如果输入从 0 开始先加 1。所有更新操作统一使用 add不要直接修改 tree。如果值域大先排序去重离散化注意排名加 1。统计类题目用 long long避免逆序对等数量溢出。树状数组大小设置为 n 1并确认 add 的边界是 n。使用二分时先确认 k 在总数范围内。测试时不仅测试查询还要测试两次更新后的结果验证动态性。生产环境若有并发写需要加锁或使用线程安全的更新方式。频繁构造大数组时避免反复初始化可以只初始化使用过的节点。6.2 典型变体区间修改与区间查询树状数组不仅能做单点更新和区间查询还能通过差分数组实现区间修改和单点查询。具体做法是维护原数组 a 的差分数组 d其中 d[i] a[i] - a[i-1]。对原数组区间 [l, r] 增加 x 等价于对 d[l] 加 x、d[r1] 减 x。此时单点查询 a[i] 等价于求 d 的前缀和。如果同时要求区间修改和区间查询需要维护两个树状数组。设差分数组 d则原数组 a 的前缀和满足sum_{i1}^n a[i] sum_{i1}^n (n - i 1) * d[i]通过维护 d[i] 和 i * d[i] 两个树状数组可以实现在 O(log n) 内完成区间修改、区间查询。这是树状数组最重要的扩展之一。6.3 二维树状数组当数据从一维扩展到二维树状数组也可以变成二维形式。二维树状数组使用tree[x][y]保存一个二维区间和更新和查询都在 x 和 y 两个维度上分别做 lowbit 跳跃复杂度为 O(log^2 n)。它适合处理子矩阵和、单点修改、区域查询等问题。如果题目数据范围很大二维数组无法直接开可以使用离散化、映射、离线处理或稀疏存储。实际工程中二维树状数组更常出现在图像处理、地理信息统计等需要按区域聚合的场景。6.4 与排序、哈希、离散化组合树状数组最强大的地方在于和排序、哈希、离散化组合。当值域无法确定时先做离散化当需要按出现次数排名时使用权值树状数组当需要统计区间内不同元素个数时可以离线按右端点排序结合树状数组维护最近出现位置。这些组合让树状数组远远不止“求前缀和”这么简单。例如求静态数组每个区间内不同数字的个数可以把查询按右端点排序从左往右扫描每个数字只在其最后一次出现的位置贡献 1其余出现位置先减再加。这样的离线处理配合树状数组可以高效回答大量区间查询。6.5 学习路径与练习建议树状数组的学习路径建议如下先手工模拟一个长度为 8 的数组手动执行 add 和 query画出每次下标移动。用模板解决纯前缀和与单点更新问题比如洛谷 P3374。用权值树状数组解决逆序对问题注意离散化。实现树状数组上的 findKth用它做动态第 k 小。学习差分数组实现区间修改 单点查询。再挑战区间修改 区间查询理解两个树状数组的维护方式。最后接触二维树状数组和离线查询问题。从练习角度看树状数组比线段树更容易掌握而且代码稳定。推荐先大量手写模板直到能在一分钟内无错误写出 add、query、findKth 三个函数。之后再学线段树你会发现线段树的很多区间合并思想与树状数组有相通之处但树状数组的简洁性依旧不可替代。实际项目中遇到单点更新加前缀统计的场景优先考虑树状数组而不是一上来就堆线段树。这样写出来的代码更短、更容易维护也更容易被同事读懂。