树状数组Fenwick Tree能在 O(log n) 时间内完成单点修改和前缀和查询而这一切都围绕一个函数lowbit。很多初学者背下了lowbit(x) x -x也背下了更新时x lowbit(x)、查询时x - lowbit(x)却不知道为什么更新要向上、查询要向下更说不清为什么两个方向都是 O(log n)。这篇文章不满足于贴模板而是用静态图示和分步推演还原整个过程把 lowbit 的二进制本质、节点管辖区间、复杂度来源一起讲清楚。读完以后你不仅能手写树状数组还能应对树状数组上二分、逆序对统计等经典扩展场景。1. 先理解 lowbit它决定每个节点的覆盖范围1.1 二进制里的 lowbit 到底取了什么lowbit(x)的结果是x的二进制表示中最低位的1以及它后面补上的所有0所组成的数值。例如x 6时二进制是110最低位的1在第1位从 0 开始计数它后面的0组成10所以lowbit(6) 2。再例如x 12二进制是1100最低位的1在第2位所以lowbit(12) 4。常用公式是int lowbit(int x) { return x -x; }在补码表示中-x等于把x按位取反再加1。x (-x)的结果正好保留了最低位的1和它后面的0。也可以用等价写法x (~x 1)但在 C 和多数语言里直接写x -x更容易记住。下面是 1 到 8 的lowbit速查表x二进制lowbit(x)覆盖区间长度111121022311114100445101116110227111118100088这张表是理解树状数组的关键。树状数组里编号为i的节点到底存了哪些元素的和完全由lowbit(i)决定。1.2 管辖区间的编号规则树状数组的tree[i]存储一段原数组区间的和。这段区间的右端点是i左端点是i - lowbit(i) 1。所以用闭区间表示就是tree[i] 管理 [i - lowbit(i) 1, i] 这一段连续区间举例i 4lowbit(4) 4所以tree[4]管理[1, 4]。i 6lowbit(6) 2所以tree[6]管理[5, 6]。i 7lowbit(7) 1所以tree[7]管理[7, 7]。i 8lowbit(8) 8所以tree[8]管理[1, 8]。可以看到lowbit(i)不仅仅是节点i的一个特征值它还直接告诉了你这个节点在树状数组里管理多长的区间。这个区间长度永远是 2 的幂这也是树状数组能把修改和查询控制在 O(log n) 的原因之一。还有一点非常重要树状数组的下标从1开始。如果下标从0开始lowbit(0) 0查询时i - lowbit(i)会一直保持0陷入死循环。所以实际使用中要么把原始数据放在数组的第1位起要么在封装时做一次下标偏移。1.3 n8 的管辖区间速查表为了后续推演方便这里列出n 8时每个节点管理的区间ilowbit(i)tree[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]从这里可以观察出两个规律所有奇数编号节点的lowbit都是1它们只管理自己一个点。编号为 2 的幂次的节点管理的区间都是从 1 开始的前缀。这两个规律在后面的更新和查询推演中会反复出现。2. 更新向上add 操作为什么是x lowbit(x)2.1 单点更新要影响哪些节点如果修改了原数组a[pos]那么所有包含了a[pos]的区间和都需要更新。也就是说所有管理区间覆盖pos的tree[i]都要加上同一个增量delta。根据管辖区间公式满足条件的i要同时满足i - lowbit(i) pos i并且i pos。直接从pos出发下一个最小的大于等于pos的合法节点是pos lowbit(pos)。这个公式不是猜测而是由低位的二进制进位规律决定的。我们把pos lowbit(pos)称为pos在树状数组中的“父节点”。于是单点更新就是不断向上走父节点直到超过数组长度n。2.2 一个例子add(3, 5)假设n 8现在要给a[3]加上5。执行过程如下初始i 3lowbit(3) 1tree[3] 5然后i 3 1 4。当前i 4lowbit(4) 4tree[4] 5然后i 4 4 8。当前i 8lowbit(8) 8tree[8] 5然后i 8 8 16。因为16 n更新结束。用一张表格分布展示步数当前 ilowbit(i)更新的节点下一步 i131tree[3]4244tree[4]8388tree[8]16为什么是这三个节点看管辖区间tree[3]管理[3, 3]包含位置 3。tree[4]管理[1, 4]包含位置 3。tree[8]管理[1, 8]包含位置 3。tree[2]管理[1, 2]不包含位置 3所以不需要更新。tree[6]管理[5, 6]也不包含位置 3。这就是“向上更新”的直观含义从叶子节点开始一步一步走到更大的覆盖区间。每一步跳到的新节点都会把当前位置包进自己的管辖范围。2.3 复杂度来源每跳一次lowbit 至少翻倍更新向上只需要证明一件事从i跳到i lowbit(i)新的lowbit至少是原来lowbit的 2 倍。设lowbit(i) 2^k说明i的二进制第k位是1而第0到第k-1位都是0。执行i lowbit(i)后第k位加1会变成0并向第k1位进位。进位之后可能在k1位产生一个1也可能继续产生连串进位但无论如何新的最低位1至少出现在第k1位。因此2^k lowbit(i) lowbit(i lowbit(i))严格来说新lowbit至少是原来的2倍。这意味着每跳一次节点管理的区间长度至少翻倍。从不超过n的某个i出发经过不超过log2(n)次跳跃就会超过n。这就是add操作 O(log n) 的来源。2.4 常见坑树状数组没有同步原数组很多初学者在读入a[i]后直接写tree[i] a[i]然后执行query发现结果不对。原因很简单如果tree[i]要管理的是一个区间那么它不能只存a[i]还要累加子区间。常见的正确做法有两种for (int i 1; i n; i) { int x; cin x; add(i, x); }或者使用后面的 O(n) 构造法。如果使用tree[i] a[i]的方式后续tree内部节点并不会自动包含所有子区间查询一定会出错。另一个常见坑是在修改原数组时只写了a[pos] delta没有调用add(pos, delta)。树状数组只认自己内部维护的tree不会因为你修改外部数组而自动感知。如果你既需要原数组又需要树状数组要在修改时同时更新两者。3. 查询向下前缀和查询为什么是x - lowbit(x)3.1 前缀和可以拆成 lowbit 区间查询前缀和sum(1..x)时目标是得到原数组前x个元素的和。树状数组的每个节点只存一段连续区间因此不能直接取某一个节点而要把[1, x]拆成若干个互不重叠的区间每个区间的右端点正好是某个树状数组节点。拆法很固定每次取当前x对应的节点tree[x]它覆盖[x - lowbit(x) 1, x]然后把x更新为x - lowbit(x)继续取下一个节点。因为下一个区间的右端点就是x - lowbit(x)且该区间和前一个区间正好首尾相接所以最终所有区间合起来就是[1, original_x]。这就是“查询向下”的含义不断把规模缩小向左向下拆区间。3.2 一个例子query(7)仍然假设n 8查询前 7 个元素的和。执行过程初始i 7lowbit(7) 1累加tree[7]然后i 7 - 1 6。当前i 6lowbit(6) 2累加tree[6]然后i 6 - 2 4。当前i 4lowbit(4) 4累加tree[4]然后i 4 - 4 0。因为i 0查询结束。最终结果是sum(1..7) tree[7] tree[6] tree[4]用表格展示步数当前 ilowbit(i)累加的节点下一步 i171tree[7]6262tree[6]4344tree[4]0对照管辖区间tree[7]管理[7, 7]tree[6]管理[5, 6]tree[4]管理[1, 4]三个区间合起来正好是[1, 7]没有重叠也没有遗漏。这就是树状数组能正确求前缀和的原因。3.3 复杂度来源每跳一次二进制去掉一个最低位的 1查询操作中i - lowbit(i)的影响在二进制下非常清晰它把i的二进制表示中最低位的1变成0。例如7的二进制是1117 - 1 6二进制是110最低位 1 被去掉6 - 2 4二进制是100最低位 1 被去掉4 - 4 0二进制是000最低位 1 被去掉一个正整数二进制中最多有floor(log2(n)) 1个二进制位所以位中1的个数不会超过 O(log n)。每跳一次至少减少一个1因此query操作最多执行 O(log n) 次循环。这就是查询为什么向下也能保证 O(log n) 的原因它不是在树的高度上一步步走而是在二进制中逐个清除最低位的1。3.4 常见坑区间和写错下标如果不小心把区间[l, r]的和写成query(r) - query(l)那么结果会少算a[l]因为query(l)包含前l个元素区间[l, r]应该用query(r) - query(l - 1)。正确的写法是int rangeSum(int l, int r) { return query(r) - query(l - 1); }这里的l - 1很容易因为紧张写错。可以牢记住一个原则前缀相减时要减到l的前一个位置。另一个坑是在query循环里把i lowbit(i)和i - lowbit(i)写反。一旦写反查询会不停向大方向跳要么越界要么结果偏大。最有效的检查方法是用一个n 8的小数组手动执行一遍更新和查询把每一步i的值打印出来。4. 最小可运行代码与对拍验证4.1 C 实现树状数组的经典封装如下#include bits/stdc.h using namespace std; int lowbit(int x) { return x -x; } class Fenwick { private: vectorint tree; int n; public: Fenwick(int n) : n(n), tree(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; } int rangeSum(int l, int r) { return query(r) - query(l - 1); } };关键点构造时数组大小是n 1下标从 1 开始。add使用idx lowbit(idx)循环条件是idx n。query使用idx - lowbit(idx)循环条件是idx 0。如果数据量很大结果可能超过int需要把tree、add的delta、query的返回值都换成long long。4.2 Python 实现Python 实现思路完全一致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 query(self, idx): res 0 while idx 0: res self.tree[idx] idx - self.lowbit(idx) return res def range_sum(self, l, r): return self.query(r) - self.query(l - 1)Python 中列表的索引从 0 开始但tree的第 0 位仍然不用所有操作从下标 1 开始。如果需要读取原数组可以在创建Fenwick后逐个调用add(i, a[i])。4.3 O(n) 构造树状数组如果对每个元素都调用一次add构造复杂度是 O(n log n)。这在某些大数据量场景下虽然也能过但更优雅的做法是 O(n) 构造vectorint buildFenwick(const vectorint a, int n) { vectorint tree(n 1, 0); for (int i 1; i n; i) { tree[i] a[i]; int j i lowbit(i); if (j n) { tree[j] tree[i]; } } return tree; }原理是tree[i]先暂存a[i]再把自己的值向父节点i lowbit(i)累加。当循环执行到父节点时父节点已经收到了所有子节点传上来的值所以最终结果和多次add完全一致。4.4 对拍验证写算法题时最稳妥的验证方法是对拍。先生成一个朴素前缀和数组作为标准答案再随机执行若干次修改和查询比较两种实现的结果是否一致。int main() { int n 8; vectorint a(n 1, 0); vectorint naive(n 1, 0); Fenwick bit(n); // 初始赋值 for (int i 1; i n; i) { a[i] rand() % 10; bit.add(i, a[i]); naive[i] naive[i - 1] a[i]; } // 随机修改 for (int step 0; step 1000; step) { int pos rand() % n 1; int delta rand() % 5 1; a[pos] delta; bit.add(pos, delta); for (int i pos; i n; i) naive[i] delta; } // 随机查询 for (int step 0; step 1000; step) { int l rand() % n 1; int r rand() % n 1; if (l r) swap(l, r); int expect naive[r] - naive[l - 1]; int actual bit.rangeSum(l, r); if (expect ! actual) { cout Mismatch at [ l , r ] endl; return 0; } } cout OK endl; return 0; }对拍脚本可以作为所有树状数组题目的基础测试工具。只要朴素实现跑得慢但正确就能用同样的随机数据验证树状数组实现是否正确。5. 三个经典应用差分区间和、树状数组上二分、逆序对5.1 区间加与区间和的差分技巧树状数组本身只支持单点修改和前缀和查询但用差分可以扩展出“区间加、区间和”的能力。维护一个差分数组d[i] a[i] - a[i - 1]。对a的区间[l, r]加上v等价于d[l] v d[r 1] - v于是单点值查询变成了差分数组的前缀和。如果还要求区间和需要再维护一个差分数组的加权前缀和。常用两个树状数组B1和B2公式为区间 [l, r] 的和 sum(r) - sum(l - 1) 其中 sum(x) (x 1) * sum(B1, x) - sum(B2, x)B1维护差分值B2维护(i - 1) * d[i]。每次区间加时add(B1, l, v) add(B1, r 1, -v) add(B2, l, (l - 1) * v) add(B2, r 1, -r * v)这个应用很经典但也很容易把公式记混。建议先在一张小数据上手动推一遍比如n 5区间[2, 4]加3观察两个树状数组的变化。5.2 树状数组上二分查找第一个前缀和大于等于 target 的位置树状数组上二分解决的问题是在值域树状数组中维护每个值出现的频次求前缀和第一次达到target的最小下标。典型场景是“查询当前所有可用元素中第 k 小的元素”。因为频次前缀和是单调不减的可以从最高位开始枚举二进制位尝试累加一块区间int findKth(int k, int n) { int idx 0; int bitMask 1; while ((bitMask 1) n) bitMask 1; for (; bitMask; bitMask 1) { int nxt idx bitMask; if (nxt n tree[nxt] k) { idx nxt; k - tree[nxt]; } } return idx 1; }核心思想如下bitMask从不超过n的最高二进制位开始。nxt idx bitMask表示尝试把一段长度为bitMask的区间纳入已经跳过的部分。如果tree[nxt] k说明从idx 1到nxt这一段的所有频次之和仍然不够k于是跳过这一段并把k减去tree[nxt]。最后idx是所有前缀和小于target的最大位置答案就是idx 1。这个算法的时间复杂度是 O(log n)而不是常见的二分套树状数组 O(log^2 n)。它依赖一个前提tree[nxt]正好表示区间(nxt - lowbit(nxt), nxt]的和而这个区间和可以被安全判断。如果维护的不是频次而是普通数值前缀和不具有单调性就不能使用这个算法。5.3 逆序对离散化后统计右边小于当前数的个数树状数组求逆序对是经典应用。设有一个序列a逆序对是满足i j且a[i] a[j]的数对(i, j)。如果值域很大直接以a[i]为下标建树状数组会浪费空间先离散化vectorint vals a; sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); for (int i 0; i n; i) { int rank lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin() 1; a[i] rank; }然后从右往左扫描把每个数加入树状数组long long ans 0; Fenwick bit(vals.size()); for (int i n - 1; i 0; i--) { ans bit.query(a[i] - 1); bit.add(a[i], 1); }每次query(a[i] - 1)统计的是已经扫描过的、值比a[i]小的元素个数。因为这些元素在原数组中出现在i的右侧且值比a[i]小正好构成逆序对。例如序列[5, 2, 6, 1]从右往左处理1query(0) 0加入 1。处理6query(5) 1因为右侧只有一个1小于 6。处理2query(1) 1因为右侧只有一个1小于 2。处理5query(4) 2因为右侧有2和1小于 5。逆序对总数是0 1 1 2 4。5.4 扩展应用的常见坑离散化时lower_bound返回的下标从 0 开始记得加 1否则树状数组会从下标 0 开始操作导致死循环或错乱。树状数组上二分时要把tree[nxt] k和nxt n同时判断。前者决定是否跳过区间后者防止数组越界。逆序对的结果在最坏情况下是n * (n - 1) / 2当n 10^5时结果约5 * 10^9已经超过int范围必须使用long long。6. 动画推演把 update 和 query 画成箭头6.1 update(3) 的路径图虽然没有真正的动画但可以按箭头顺序把更新过程画成一张路径图update(3) 3 | | lowbit(3)1 v 4 | | lowbit(4)4 v 8 | | lowbit(8)8 v 16 (超出 n结束)对应的路径用节点编号表示是3 - 4 - 8 - 16这张图非常直观地展示了“向上”的含义每次跳到更大的节点编号。再看一次所有奇数节点的更新路径1 - 2 - 4 - 8 - 16 3 - 4 - 8 - 16 5 - 6 - 8 - 16 7 - 8 - 16可以发现路径长度最多等于二进制位的个数。树状数组不是普通二叉树但更新路径却有类似树的高度约束。6.2 query(7) 的路径图查询是另一个方向query(7) 7 | | -lowbit(7)1 v 6 | | -lowbit(6)2 v 4 | | -lowbit(4)4 v 0 (结束)用节点编号表示7 - 6 - 4 - 0对应累加的节点是tree[7]、tree[6]、tree[4]。如果把管辖区间标出来就是[7,7] [5,6] [1,4]从上到下拼接后正好是[1,7]。这张“动画图”比文字描述更容易让初学者理解查询不是在树上沿父子边走而是在不断扔掉二进制最低位的 1把一个大前缀拆成几个 lowbit 区间。6.3 结果不对时的排查链路树状数组的代码很短一旦结果不对通常只有几个原因。建议按下面的顺序排查问题现象可能原因检查方式处理建议查询结果偏小l和r的区间和写成了query(r) - query(l)打印query(l)和query(r)改为query(r) - query(l - 1)更新后查询不变修改原数组后没有调用add检查是否执行a[pos] delta; add(pos, delta);每次修改都要同步调用add程序死循环下标从 0 开始或lowbit(0)0打印循环里的idx下标从 1 开始数组大小n 1更新和查询方向写反add里用了idx - lowbit(idx)对照模板逐行检查更新向上查询向下大数据量答案溢出使用int存储累加和检查tree类型改用long long离散化后结果错rank从 0 开始打印rank序列lower_bound结果加 1排查顺序的建议是先看下标边界再看循环方向然后检查区间相减公式最后检查数据类型。大多数错误出现在这几处而且都可以通过打印中间变量快速发现。6.4 可复用清单每次写树状数组题目时可以用下面这份清单做检查树状数组大小是否为n 1或n 2预留了第 0 位。所有操作下标是否从 1 开始原数组下标是否需要统一偏移。lowbit函数是否写成x -x不要写成x x。add循环条件是不是idx n每次是否idx lowbit(idx)。query循环条件是不是idx 0每次是否idx - lowbit(idx)。区间和是否写成query(r) - query(l - 1)。多组测试数据时tree是否正确清空。涉及计数、逆序对、区间累计时是否使用long long。值域很大时是否先离散化并且离散化下标从 1 开始。使用树状数组上二分时是否确认维护的前缀和具有单调性。清单上的每一项都对应真实踩过的坑。写完后按清单扫一遍能省下大量调试时间。6.5 学习环境与 OJ/生产环境的差异学习阶段可以在本地环境打印tree数组、idx变化和中间结果这个过程对理解算法非常有帮助。比如在add循环里加一行调试输出观察每次跳转的idx比单纯看代码更直观。OJ 环境更关注输入输出效率和内存占用。树状数组通常用数组实现不要频繁new多组数据时及时清空。如果使用 Python注意递归和循环性能树状数组本身就是循环通常还好。如果把树状数组放到生产环境的服务里需要额外考虑数据规模、线程安全和持久化。树状数组适合内存中高频读写且数据规模可控的场景不适合直接当作分布式计数器。生产环境还会涉及日志、监控和回滚算法代码通常只是其中一个很小的组件。这里只提示一点树状数组的下标偏移和边界处理在接入真实数据后一定要用脏数据和生产样例做回归。7. 复杂度再证明与下一步选型7.1 更新与查询的统一视角进位和去最低位 1把两个操作放到二进制视角下看更新向上x lowbit(x)等价于把二进制中的最低位 1 不断“进位”。每进位一次lowbit 至少翻倍所以最多执行 O(log n) 次。查询向下x - lowbit(x)等价于把二进制中的最低位 1 变回 0。每执行一次二进制中 1 的个数减少一个所以最多执行 O(log n) 次。一个是“加”一个是“减”方向相反但都通过 lowbit 保持对数复杂度。这也解释了为什么树状数组特别依赖二进制。它不使用显式树结构而是把数组下标本身当成一棵逻辑树来使用。7.2 为什么说 O(log n) 而不是 O(log 值域)树状数组的复杂度通常写成 O(log n)其中n是数组长度也是下标的最大值。更准确地说循环次数与n的二进制位数有关也就是floor(log2(n)) 1。比如n 8二进制位数是 4更新和查询最多 4 步。n 10^5二进制位数约 17循环次数不超过 17。这比n本身小得多所以称为 O(log n) 是合理的。有些资料会写 O(log N)这里的N可能是值域大小。如果使用离散化N被压缩成不同元素个数仍然不超过原数组长度所以复杂度含义一致。树状数组上二分的复杂度也是 O(log n)因为它本质上只做了一次从高到低的二进制枚举而不是每次二分都查询一次前缀和。7.3 自测练习理解不能只停留在阅读层面建议做下面几个小练习手写n 16的管辖区间表验证tree[10]管理的是[9, 10]还是[7, 10]。对[1, 2, 3, 4, 5]执行add(3, 1)列出所有被修改的tree[i]以及每个tree[i]的最终值。对同一数组执行query(5)把每一步的i和累加的tree[i]写下来判断结果是否等于 15。用离散化求[3, 1, 4, 1, 5, 9, 2, 6]的逆序对数量并与暴力 O(n^2) 结果对拍。实现findKth在值域树状数组中依次插入若干数查找第k小元素。这些练习覆盖了更新、查询、离散化、上二分四个核心能力。每完成一个都把执行路径画成前文那样的箭头图会更容易形成长期记忆。7.4 什么时候该换线段树树状数组不是万能的。它擅长维护“前缀和”这类满足结合律且容易用 lowbit 拆分成区间的信息但也有一些明显不适用的场景场景树状数组线段树单点修改 区间和推荐可以区间修改 区间和用差分技巧可以推荐区间最大值/最小值一般不适合推荐区间最值 区间赋值很难实现推荐动态开点/离散化复杂区间实现繁琐更灵活如果你需要维护的信息无法通过 lowbit 拆分或者需要懒标记、区间覆盖、最大值等复杂标记线段树通常更合适。树状数组的优势是代码短、常数小、容易调试在能用前缀和思路解决的问题上优先使用树状数组是合理的工程选择。如果能把 lowbit 看懂把更新向上、查询向下两条路径理解成“进位”和“去最低位 1”那么树状数组的复杂度证明、代码边界、常见错误都会变得很容易定位。下一步建议用一组随机数据对拍把本文中的路径图亲手画一遍再去做逆序对和值域上二分的题目你会发现这类“碰运气模板”的问题其实有非常清晰的规律。