树状数组是一个经常被低估的数据结构。它没有线段树那么长的代码却能以O(log n)的代价完成单点更新和前缀查询空间只需要O(n)。很多算法题、竞赛题和面试题里树状数组都是“代码短、常数小、容易扩展”的标配。本文以lowbit为主线把“更新向上、查询向下”的底层原因彻底拆开再带你把树状数组上二分、逆序对计数这两个高频场景完整跑通。这篇文章不是单纯背模板而是把原理、实现、测试、进阶层层展开读完你会知道lowbit为什么是x (-x)更新为什么往高位走查询为什么往低位收以及为什么两者的复杂度都是O(log n)。文中所有代码都按可运行模板给出配合测试用例可以直接在本地验证。适合刚开始学树状数组的同学也适合秋招前想系统回顾数据结构的读者。1. 核心能力速览项目说明算法名称树状数组Fenwick Tree / Binary Indexed Tree核心操作单点更新、前缀和查询、区间和查询时间复杂度单次更新O(log n)单次查询O(log n)空间复杂度O(n)额外数组空间核心概念lowbit(x)二进制下最低位 1 对应的值经典应用动态前缀和、区间和、逆序对计数、第 k 小查询进阶能力配合差分实现区间修改 区间查询树状数组上二分语言支持C/C、Java、Python、Rust 等均可实现推荐学习方式手动画出二进制拆段过程再对照代码跑一遍测试树状数组最核心的公式只有一行int lowbit(int x) { return x (-x); }后面的更新、查询、二分全部围绕这行代码展开。先把这一行吃透整个数据结构就通了大半。2. 适用场景与使用边界树状数组适合解决可以前缀拆分、支持逆运算的问题。最常见的场景是单点更新前缀查询比如维护一个数组支持修改某个位置的值并查询前i个位置的和。区间和查询用query(r) - query(l - 1)即可得到区间和。逆序对计数在线扫描数组用计数数组快速统计“当前元素之前有多少个比它大”。动态第 k 小配合计数数组和树状数组上二分可以在O(log n)内求第 k 小元素。区间修改 区间查询用两个树状数组维护差分序列一次区间修改也能压到O(log n)。但是树状数组不是万能的。以下场景需要慎重频繁区间取最大值、最小值树状数组适合可减运算比如和、异或。维护最值时如果只做单点更新可以用额外技巧但区间更新往往需要线段树或分块。需要删除任意区间、合并两个有序序列这类动态线性结构更适合平衡树树状数组本身不支持复杂重构。只是静态前缀和直接用普通前缀和数组即可单次查询O(1)没必要引入树状数组。值域很大且没有离散化树状数组下标天然依赖1..n这个范围如果值是10^9级别必须先离散化。使用边界同样要留意树状数组维护的运算必须满足结合律并且能通过两个前缀结果“抵消”出区间结果。典型的安全操作是加法、异或、乘法求逆时要注意模数维护取模结果时要保证每一步运算都符合模运算规则。3. 环境准备与代码模板搭建树状数组不依赖任何特殊环境。本地随便一个支持 C11 的编译器都能跑也可以用在线 OJ 的右侧代码面板直接验证。这里给出 C 和 Python 两版模板后面所有实战代码都以这两套模板为基础。3.1 C 基础模板#include bits/stdc.h using namespace std; const int MAXN 100005; int n; // 数组实际大小 long long bit[MAXN]; // 树状数组 int lowbit(int x) { return x (-x); } // 单点更新位置 i 增加 v void add(int i, int v) { for (; i n; i lowbit(i)) { bit[i] v; } } // 前缀查询返回 [1, i] 的和 long long query(int i) { long long res 0; for (; i 0; i - lowbit(i)) { res bit[i]; } return res; } // 区间查询[l, r] 的和 long long range_query(int l, int r) { return query(r) - query(l - 1); }3.2 Python 基础模板n 100005 bit [0] * (n 1) def lowbit(x): return x -x def add(i, v): while i n: bit[i] v i lowbit(i) def query(i): res 0 while i 0: res bit[i] i - lowbit(i) return res模板里有两个关键动作add循环是i lowbit(i)方向向上。query循环是i - lowbit(i)方向向下。如果你把这两个方向记反了程序并不会报错但结果会完全错乱。下一节专门解释为什么方向必须这么走。4. lowbit 推导更新向上、查询向下的底层原因lowbit(x)的作用是取出x的二进制表示中最低位的1所对应的数值。例如3的二进制是0011最低位 1 对应0001所以lowbit(3) 1。4的二进制是0100最低位 1 对应0100所以lowbit(4) 4。6的二进制是0110最低位 1 对应0010所以lowbit(6) 2。计算方式就是x (-x)。因为-x在补码表示下等于~x 1它会把原来最低位的 1 保留下来把更高位全部取反。比如6 (-6)6是00000110-6是11111010相与正好得到00000010也就是2。我们可以把lowbit和树状数组覆盖区间对应起来bit[i]维护的是原数组a在区间[i - lowbit(i) 1, i]上的和。i二进制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]这张表是理解树状数组的钥匙。更新为什么向上假设a[3]变化了那么哪些区间覆盖了3答案是[3,3]、[1,4]、[1,8]对应下标就是3、4、8。从3出发第一步3 lowbit(3) 4第二步4 lowbit(4) 8。每一步都在把当前下标二进制中最低位的 1 向前进位。看一下二进制的轨迹3 0011 4 0100 8 1000每次更新都让最低位的 1 向左移动直到超过n。这个“覆盖当前位置的祖先链”就是更新时走过的路径。查询为什么向下查询前缀[1, 7]时不能直接拿一个bit节点表示整段和。树状数组的做法是把7的二进制拆成若干段7 0111 0100 0010 0001对应到树状数组节点就是bit[7] 覆盖 [7,7] bit[6] 覆盖 [5,6] bit[4] 覆盖 [1,4]所以query(7) bit[7] bit[6] bit[4]。查询路径是7 - 6 - 4 - 0每一步都减去lowbit(i)等价于把当前二进制的最低位的 1 去掉。从高位看查询是在不断“向下收集”互不重叠的完整区间块。为什么都是 O(log n)因为一个整数在二进制下最多有O(log n)个 bit。update每步让最低位的 1 左移一次query每步去掉一个 1。无论哪种操作迭代次数都不会超过二进制位数也就是O(log n)。5. 核心操作完整拆解单点更新与前缀查询光看路径还不够我们用一个具体数组跑一遍。设int a[9] {0, 1, 2, 3, 4, 5, 6, 7, 8};从下标 1 开始依次调用add(i, a[i])建树。建完后bit数组为bit[1] 1 bit[2] 3 bit[3] 3 bit[4] 10 bit[5] 5 bit[6] 11 bit[7] 7 bit[8] 36先验证query(7)query(7) bit[7] bit[6] bit[4] 7 11 10 28原数组前 7 个元素和确实是1 2 3 4 5 6 7 28。现在执行add(3, 10)。更新路径是3 - 4 - 8所以只有bit[3]、bit[4]、bit[8]发生变化bit[3] 13 bit[4] 20 bit[8] 46再查query(7)query(7) 7 11 20 38因为a[3]增加了 10前缀和也相应多了 10结果验证通过。这个例子说明更新只影响覆盖这个位置的那几个祖先节点查询只读取前缀拆出的几个完整区间块。可以写一个main函数做自动化验证int main() { n 8; int a[9] {0, 1, 2, 3, 4, 5, 6, 7, 8}; for (int i 1; i n; i) { add(i, a[i]); } cout query(7) query(7) endl; // 28 add(3, 10); cout query(7) query(7) endl; // 38 cout query(3) - query(2) range_query(3, 3) endl; // 13 return 0; }区间查询[l, r]的公式就是query(r) - query(l - 1)。这依赖加法存在逆运算所以树状数组天然适合做求和、异或这类问题。6. 进阶实战一区间修改与区间查询现在升级需求我们要支持区间[l, r]整体加上一个值同时还能查询区间和。如果只用一个普通树状数组一次区间修改往往要拆成单点更新复杂度会退化。解决办法是引入差分数组。设原始数组为a差分数组为d[i] a[i] - a[i-1]。那么前缀和可以展开sum(1..x) a[1] a[2] ... a[x] (x 1) * sum(d[1..x]) - sum(1 * d[1] 2 * d[2] ... x * d[x])所以我们维护两个树状数组bit1维护差分数组d[i]bit2维护i * d[i]区间[l, r]加v时差分数组的变化是d[l] v、d[r1] - v对应两个树状数组的操作void range_add(int l, int r, long long v) { add(bit1, l, v); add(bit1, r 1, -v); add(bit2, l, 1LL * l * v); add(bit2, r 1, -1LL * (r 1) * v); } long long prefix_sum(int x) { return 1LL * (x 1) * query(bit1, x) - query(bit2, x); } long long range_query(int l, int r) { return prefix_sum(r) - prefix_sum(l - 1); }注意这里add和query需要支持传入不同树状数组实际使用时可以写成带数组参数的版本也可以拆成add1、add2、query1、query2。关键是bit2维护的是i * d[i]而不是d[i]本身很多人在这一步写错。验证一下设n 8初始数组全为 0。执行range_add(2, 5, 3)原数组第 2 到第 5 位都变成 3。range_query(1, 4)应该等于第 2、3、4 位的和也就是 9。range_query(2, 5)应该等于 12。range_query(6, 8)应该等于 0。因为差分数组在修改后变成d[2]3, d[6]-3用上面的prefix_sum公式计算时两端会自然抵消。这个模板是“区间修改 区间查询”的标准解法比线段树代码短很多。7. 进阶实战二树状数组上二分求第 k 小树状数组上二分是一个很实用的技巧。常见场景是维护一个动态计数数组cnt[x]表示值x出现了几次。插入一个数就是add(x, 1)删除一个数就是add(x, -1)。此时query(x)表示不大于x的元素个数。如果要从这些动态数字中快速找到第k小的值普通做法是先二分x再查query(x)复杂度是O(log^2 n)。但树状数组本身的结构允许我们直接沿着二进制位跳做到单次O(log n)。核心思想是从高到低枚举二进制位判断当前位置加上这一步后累加到的区间和是否仍然小于k。如果小于说明目标位置还在右边就把pos移过去并累加否则不动。代码如下// 前提维护的计数必须非负且存在第 k 小 int find_kth(int k) { int pos 0; int max_step 1; while ((max_step 1) n) { max_step 1; } for (int step max_step; step 0; step 1) { int nxt pos step; if (nxt n bit[nxt] k) { pos nxt; k - bit[nxt]; } } return pos 1; }为什么可以这样跳因为bit[nxt]覆盖的区间长度就是lowbit(nxt)它恰好对应二进制拆分中的一段。我们从大到小枚举step相当于判断“跳过当前这一段之后累加前缀和是否还小于 k”。把所有可以跳过的段都跳过去剩下的位置就是第一个让前缀和大于等于k的下标。测试一下初始计数数组为空依次插入2、5、5、7这四个数。此时元素集合是{2, 5, 5, 7}。find_kth(1)返回 2。find_kth(3)返回 5。find_kth(4)返回 7。如果插入的值域比较大需要先离散化然后把离散化后的排名作为下标插入树状数组。这个技巧在动态求第 k 大、求流式中位数、以及某些离线数据结构题里非常好用。8. 进阶实战三逆序对计数与批量测试逆序对是树状数组的经典应用。问题是给定一个长度为n的数组统计有多少对(i, j)满足i j且a[i] a[j]。朴素做法是双重循环复杂度O(n^2)数据规模稍大就不行。树状数组的做法是先离散化再用“计数数组 前缀和”在线统计。有两种扫描方向这里推荐从右往左扫对原数组排序去重得到排名数组。从右往左遍历原数组每次先查询“已经出现的、小于当前值”的个数加入答案。再把当前值对应的计数加 1。核心代码如下#include bits/stdc.h using namespace std; const int MAXN 100005; int n; long long bit[MAXN]; int lowbit(int x) { return x (-x); } void add(int i, int v) { for (; i n; i lowbit(i)) bit[i] v; } long long query(int i) { long long res 0; for (; i 0; i - lowbit(i)) res bit[i]; return res; } long long count_inversions(vectorint a) { vectorint vals a; sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); long long ans 0; // 从右往左右侧已经出现的元素里小于当前值的个数就是逆序对数 for (int i a.size() - 1; i 0; i--) { int rank lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin() 1; ans query(rank - 1); add(rank, 1); } return ans; } int main() { vectorint a {3, 1, 2}; cout 逆序对数 count_inversions(a) endl; // 2 return 0; }验证{3, 1, 2}从右往左看到2排名是 2query(1) 0答案 0然后add(2, 1)。看到1排名是 1query(0) 0答案 0然后add(1, 1)。看到3排名是 3query(2) 2答案 2然后add(3, 1)。结果 2 正确。因为3 1且3 2。实际做题时经常需要和暴力写法对拍。批量测试的思路是随机生成多组小规模数组一个用树状数组求一个用双层循环求然后对比结果。如果所有随机数据都一致基本可以断定实现正确。long long brute_force(vectorint a) { long long ans 0; for (int i 0; i a.size(); i) { for (int j i 1; j a.size(); j) { if (a[i] a[j]) ans; } } return ans; }对拍时注意把n调小一点比如n 50方便快速检查。9. 复杂度观察、常见问题与最佳实践9.1 复杂度与性能观察树状数组的复杂度非常稳定操作复杂度单点更新O(log n)前缀查询O(log n)区间查询O(log n)区间修改 区间查询O(log n)树状数组上二分O(log n)逆序对计数O(n log n)建树循环 addO(n log n)建树O(n) 递推法O(n)如果对建树效率有要求可以用下面这个 O(n) 建树方法void build(int a[], int n) { for (int i 1; i n; i) { bit[i] a[i]; int j i lowbit(i); if (j n) bit[j] bit[i]; } }原理是让父节点直接累加子区间避免每个元素都独立走一次add。实际在 OJ 上跑的时候n 10^5到10^6的规模下树状数组的常数非常小一组测试数据通常只需几毫秒到几十毫秒。相比之下线段树因为要维护左右子树和递归调用常数会明显更大。这也是“能树状数组就不线段树”的由来。如果要观察性能瓶颈重点看三处是否做了不必要的离散化排序。是否在循环内频繁调用query导致整体变成O(n log^2 n)。是否把中间结果错存成了int导致溢出后不断出错。9.2 常见问题与排查方法问题现象可能原因排查方式解决方案add之后查询结果没变化add的循环写成了i - lowbit(i)打印add过程中的下标序列改为i lowbit(i)query返回结果偏大或偏小query的循环写成了i lowbit(i)打印query过程中的下标序列改为i - lowbit(i)程序死循环或数组越界下标从 0 开始或循环边界没控制检查索引起点和循环条件下标从 1 开始add里加i n判断区间查询结果不对没有使用query(r) - query(l - 1)单测[l, r]小数据确认l 1后相减逆序对答案溢出答案是long long但中途用了int打印ans的变化过程统一使用long long值域过大数组开不下未做离散化检查原始值范围排序去重后使用排名下标树状数组上二分结果不对维护的计数存在负数检查插入和删除逻辑只对非负计数使用该二分取模结果不对add和query的取模时机不一致手动模拟小数取模统一在累加后取模并处理负数调试树状数组有个很有效的技巧设计一个debug函数把bit[1..n]全部打印出来然后手动计算每个lowbit覆盖的区间对比纸面上的模拟结果。树状数组的下标链路很短打印一两轮就能定位是方向写反还是边界写错。9.3 最佳实践与使用建议背模板前先背原理。lowbit到底在干什么update为什么向上query为什么向下这三个问题比代码本身重要。所有下标从 1 开始数组 
长河君 · 2026/8/31 8:03:26 · 阅读 1.2k 树状数组原理与高频应用：从lowbit到逆序对计数
树状数组是一个经常被低估的数据结构。它没有线段树那么长的代码却能以O(log n)的代价完成单点更新和前缀查询空间只需要O(n)。很多算法题、竞赛题和面试题里树状数组都是“代码短、常数小、容易扩展”的标配。本文以lowbit为主线把“更新向上、查询向下”的底层原因彻底拆开再带你把树状数组上二分、逆序对计数这两个高频场景完整跑通。这篇文章不是单纯背模板而是把原理、实现、测试、进阶层层展开读完你会知道lowbit为什么是x (-x)更新为什么往高位走查询为什么往低位收以及为什么两者的复杂度都是O(log n)。文中所有代码都按可运行模板给出配合测试用例可以直接在本地验证。适合刚开始学树状数组的同学也适合秋招前想系统回顾数据结构的读者。1. 核心能力速览项目说明算法名称树状数组Fenwick Tree / Binary Indexed Tree核心操作单点更新、前缀和查询、区间和查询时间复杂度单次更新O(log n)单次查询O(log n)空间复杂度O(n)额外数组空间核心概念lowbit(x)二进制下最低位 1 对应的值经典应用动态前缀和、区间和、逆序对计数、第 k 小查询进阶能力配合差分实现区间修改 区间查询树状数组上二分语言支持C/C、Java、Python、Rust 等均可实现推荐学习方式手动画出二进制拆段过程再对照代码跑一遍测试树状数组最核心的公式只有一行int lowbit(int x) { return x (-x); }后面的更新、查询、二分全部围绕这行代码展开。先把这一行吃透整个数据结构就通了大半。2. 适用场景与使用边界树状数组适合解决可以前缀拆分、支持逆运算的问题。最常见的场景是单点更新前缀查询比如维护一个数组支持修改某个位置的值并查询前i个位置的和。区间和查询用query(r) - query(l - 1)即可得到区间和。逆序对计数在线扫描数组用计数数组快速统计“当前元素之前有多少个比它大”。动态第 k 小配合计数数组和树状数组上二分可以在O(log n)内求第 k 小元素。区间修改 区间查询用两个树状数组维护差分序列一次区间修改也能压到O(log n)。但是树状数组不是万能的。以下场景需要慎重频繁区间取最大值、最小值树状数组适合可减运算比如和、异或。维护最值时如果只做单点更新可以用额外技巧但区间更新往往需要线段树或分块。需要删除任意区间、合并两个有序序列这类动态线性结构更适合平衡树树状数组本身不支持复杂重构。只是静态前缀和直接用普通前缀和数组即可单次查询O(1)没必要引入树状数组。值域很大且没有离散化树状数组下标天然依赖1..n这个范围如果值是10^9级别必须先离散化。使用边界同样要留意树状数组维护的运算必须满足结合律并且能通过两个前缀结果“抵消”出区间结果。典型的安全操作是加法、异或、乘法求逆时要注意模数维护取模结果时要保证每一步运算都符合模运算规则。3. 环境准备与代码模板搭建树状数组不依赖任何特殊环境。本地随便一个支持 C11 的编译器都能跑也可以用在线 OJ 的右侧代码面板直接验证。这里给出 C 和 Python 两版模板后面所有实战代码都以这两套模板为基础。3.1 C 基础模板#include bits/stdc.h using namespace std; const int MAXN 100005; int n; // 数组实际大小 long long bit[MAXN]; // 树状数组 int lowbit(int x) { return x (-x); } // 单点更新位置 i 增加 v void add(int i, int v) { for (; i n; i lowbit(i)) { bit[i] v; } } // 前缀查询返回 [1, i] 的和 long long query(int i) { long long res 0; for (; i 0; i - lowbit(i)) { res bit[i]; } return res; } // 区间查询[l, r] 的和 long long range_query(int l, int r) { return query(r) - query(l - 1); }3.2 Python 基础模板n 100005 bit [0] * (n 1) def lowbit(x): return x -x def add(i, v): while i n: bit[i] v i lowbit(i) def query(i): res 0 while i 0: res bit[i] i - lowbit(i) return res模板里有两个关键动作add循环是i lowbit(i)方向向上。query循环是i - lowbit(i)方向向下。如果你把这两个方向记反了程序并不会报错但结果会完全错乱。下一节专门解释为什么方向必须这么走。4. lowbit 推导更新向上、查询向下的底层原因lowbit(x)的作用是取出x的二进制表示中最低位的1所对应的数值。例如3的二进制是0011最低位 1 对应0001所以lowbit(3) 1。4的二进制是0100最低位 1 对应0100所以lowbit(4) 4。6的二进制是0110最低位 1 对应0010所以lowbit(6) 2。计算方式就是x (-x)。因为-x在补码表示下等于~x 1它会把原来最低位的 1 保留下来把更高位全部取反。比如6 (-6)6是00000110-6是11111010相与正好得到00000010也就是2。我们可以把lowbit和树状数组覆盖区间对应起来bit[i]维护的是原数组a在区间[i - lowbit(i) 1, i]上的和。i二进制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]这张表是理解树状数组的钥匙。更新为什么向上假设a[3]变化了那么哪些区间覆盖了3答案是[3,3]、[1,4]、[1,8]对应下标就是3、4、8。从3出发第一步3 lowbit(3) 4第二步4 lowbit(4) 8。每一步都在把当前下标二进制中最低位的 1 向前进位。看一下二进制的轨迹3 0011 4 0100 8 1000每次更新都让最低位的 1 向左移动直到超过n。这个“覆盖当前位置的祖先链”就是更新时走过的路径。查询为什么向下查询前缀[1, 7]时不能直接拿一个bit节点表示整段和。树状数组的做法是把7的二进制拆成若干段7 0111 0100 0010 0001对应到树状数组节点就是bit[7] 覆盖 [7,7] bit[6] 覆盖 [5,6] bit[4] 覆盖 [1,4]所以query(7) bit[7] bit[6] bit[4]。查询路径是7 - 6 - 4 - 0每一步都减去lowbit(i)等价于把当前二进制的最低位的 1 去掉。从高位看查询是在不断“向下收集”互不重叠的完整区间块。为什么都是 O(log n)因为一个整数在二进制下最多有O(log n)个 bit。update每步让最低位的 1 左移一次query每步去掉一个 1。无论哪种操作迭代次数都不会超过二进制位数也就是O(log n)。5. 核心操作完整拆解单点更新与前缀查询光看路径还不够我们用一个具体数组跑一遍。设int a[9] {0, 1, 2, 3, 4, 5, 6, 7, 8};从下标 1 开始依次调用add(i, a[i])建树。建完后bit数组为bit[1] 1 bit[2] 3 bit[3] 3 bit[4] 10 bit[5] 5 bit[6] 11 bit[7] 7 bit[8] 36先验证query(7)query(7) bit[7] bit[6] bit[4] 7 11 10 28原数组前 7 个元素和确实是1 2 3 4 5 6 7 28。现在执行add(3, 10)。更新路径是3 - 4 - 8所以只有bit[3]、bit[4]、bit[8]发生变化bit[3] 13 bit[4] 20 bit[8] 46再查query(7)query(7) 7 11 20 38因为a[3]增加了 10前缀和也相应多了 10结果验证通过。这个例子说明更新只影响覆盖这个位置的那几个祖先节点查询只读取前缀拆出的几个完整区间块。可以写一个main函数做自动化验证int main() { n 8; int a[9] {0, 1, 2, 3, 4, 5, 6, 7, 8}; for (int i 1; i n; i) { add(i, a[i]); } cout query(7) query(7) endl; // 28 add(3, 10); cout query(7) query(7) endl; // 38 cout query(3) - query(2) range_query(3, 3) endl; // 13 return 0; }区间查询[l, r]的公式就是query(r) - query(l - 1)。这依赖加法存在逆运算所以树状数组天然适合做求和、异或这类问题。6. 进阶实战一区间修改与区间查询现在升级需求我们要支持区间[l, r]整体加上一个值同时还能查询区间和。如果只用一个普通树状数组一次区间修改往往要拆成单点更新复杂度会退化。解决办法是引入差分数组。设原始数组为a差分数组为d[i] a[i] - a[i-1]。那么前缀和可以展开sum(1..x) a[1] a[2] ... a[x] (x 1) * sum(d[1..x]) - sum(1 * d[1] 2 * d[2] ... x * d[x])所以我们维护两个树状数组bit1维护差分数组d[i]bit2维护i * d[i]区间[l, r]加v时差分数组的变化是d[l] v、d[r1] - v对应两个树状数组的操作void range_add(int l, int r, long long v) { add(bit1, l, v); add(bit1, r 1, -v); add(bit2, l, 1LL * l * v); add(bit2, r 1, -1LL * (r 1) * v); } long long prefix_sum(int x) { return 1LL * (x 1) * query(bit1, x) - query(bit2, x); } long long range_query(int l, int r) { return prefix_sum(r) - prefix_sum(l - 1); }注意这里add和query需要支持传入不同树状数组实际使用时可以写成带数组参数的版本也可以拆成add1、add2、query1、query2。关键是bit2维护的是i * d[i]而不是d[i]本身很多人在这一步写错。验证一下设n 8初始数组全为 0。执行range_add(2, 5, 3)原数组第 2 到第 5 位都变成 3。range_query(1, 4)应该等于第 2、3、4 位的和也就是 9。range_query(2, 5)应该等于 12。range_query(6, 8)应该等于 0。因为差分数组在修改后变成d[2]3, d[6]-3用上面的prefix_sum公式计算时两端会自然抵消。这个模板是“区间修改 区间查询”的标准解法比线段树代码短很多。7. 进阶实战二树状数组上二分求第 k 小树状数组上二分是一个很实用的技巧。常见场景是维护一个动态计数数组cnt[x]表示值x出现了几次。插入一个数就是add(x, 1)删除一个数就是add(x, -1)。此时query(x)表示不大于x的元素个数。如果要从这些动态数字中快速找到第k小的值普通做法是先二分x再查query(x)复杂度是O(log^2 n)。但树状数组本身的结构允许我们直接沿着二进制位跳做到单次O(log n)。核心思想是从高到低枚举二进制位判断当前位置加上这一步后累加到的区间和是否仍然小于k。如果小于说明目标位置还在右边就把pos移过去并累加否则不动。代码如下// 前提维护的计数必须非负且存在第 k 小 int find_kth(int k) { int pos 0; int max_step 1; while ((max_step 1) n) { max_step 1; } for (int step max_step; step 0; step 1) { int nxt pos step; if (nxt n bit[nxt] k) { pos nxt; k - bit[nxt]; } } return pos 1; }为什么可以这样跳因为bit[nxt]覆盖的区间长度就是lowbit(nxt)它恰好对应二进制拆分中的一段。我们从大到小枚举step相当于判断“跳过当前这一段之后累加前缀和是否还小于 k”。把所有可以跳过的段都跳过去剩下的位置就是第一个让前缀和大于等于k的下标。测试一下初始计数数组为空依次插入2、5、5、7这四个数。此时元素集合是{2, 5, 5, 7}。find_kth(1)返回 2。find_kth(3)返回 5。find_kth(4)返回 7。如果插入的值域比较大需要先离散化然后把离散化后的排名作为下标插入树状数组。这个技巧在动态求第 k 大、求流式中位数、以及某些离线数据结构题里非常好用。8. 进阶实战三逆序对计数与批量测试逆序对是树状数组的经典应用。问题是给定一个长度为n的数组统计有多少对(i, j)满足i j且a[i] a[j]。朴素做法是双重循环复杂度O(n^2)数据规模稍大就不行。树状数组的做法是先离散化再用“计数数组 前缀和”在线统计。有两种扫描方向这里推荐从右往左扫对原数组排序去重得到排名数组。从右往左遍历原数组每次先查询“已经出现的、小于当前值”的个数加入答案。再把当前值对应的计数加 1。核心代码如下#include bits/stdc.h using namespace std; const int MAXN 100005; int n; long long bit[MAXN]; int lowbit(int x) { return x (-x); } void add(int i, int v) { for (; i n; i lowbit(i)) bit[i] v; } long long query(int i) { long long res 0; for (; i 0; i - lowbit(i)) res bit[i]; return res; } long long count_inversions(vectorint a) { vectorint vals a; sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); long long ans 0; // 从右往左右侧已经出现的元素里小于当前值的个数就是逆序对数 for (int i a.size() - 1; i 0; i--) { int rank lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin() 1; ans query(rank - 1); add(rank, 1); } return ans; } int main() { vectorint a {3, 1, 2}; cout 逆序对数 count_inversions(a) endl; // 2 return 0; }验证{3, 1, 2}从右往左看到2排名是 2query(1) 0答案 0然后add(2, 1)。看到1排名是 1query(0) 0答案 0然后add(1, 1)。看到3排名是 3query(2) 2答案 2然后add(3, 1)。结果 2 正确。因为3 1且3 2。实际做题时经常需要和暴力写法对拍。批量测试的思路是随机生成多组小规模数组一个用树状数组求一个用双层循环求然后对比结果。如果所有随机数据都一致基本可以断定实现正确。long long brute_force(vectorint a) { long long ans 0; for (int i 0; i a.size(); i) { for (int j i 1; j a.size(); j) { if (a[i] a[j]) ans; } } return ans; }对拍时注意把n调小一点比如n 50方便快速检查。9. 复杂度观察、常见问题与最佳实践9.1 复杂度与性能观察树状数组的复杂度非常稳定操作复杂度单点更新O(log n)前缀查询O(log n)区间查询O(log n)区间修改 区间查询O(log n)树状数组上二分O(log n)逆序对计数O(n log n)建树循环 addO(n log n)建树O(n) 递推法O(n)如果对建树效率有要求可以用下面这个 O(n) 建树方法void build(int a[], int n) { for (int i 1; i n; i) { bit[i] a[i]; int j i lowbit(i); if (j n) bit[j] bit[i]; } }原理是让父节点直接累加子区间避免每个元素都独立走一次add。实际在 OJ 上跑的时候n 10^5到10^6的规模下树状数组的常数非常小一组测试数据通常只需几毫秒到几十毫秒。相比之下线段树因为要维护左右子树和递归调用常数会明显更大。这也是“能树状数组就不线段树”的由来。如果要观察性能瓶颈重点看三处是否做了不必要的离散化排序。是否在循环内频繁调用query导致整体变成O(n log^2 n)。是否把中间结果错存成了int导致溢出后不断出错。9.2 常见问题与排查方法问题现象可能原因排查方式解决方案add之后查询结果没变化add的循环写成了i - lowbit(i)打印add过程中的下标序列改为i lowbit(i)query返回结果偏大或偏小query的循环写成了i lowbit(i)打印query过程中的下标序列改为i - lowbit(i)程序死循环或数组越界下标从 0 开始或循环边界没控制检查索引起点和循环条件下标从 1 开始add里加i n判断区间查询结果不对没有使用query(r) - query(l - 1)单测[l, r]小数据确认l 1后相减逆序对答案溢出答案是long long但中途用了int打印ans的变化过程统一使用long long值域过大数组开不下未做离散化检查原始值范围排序去重后使用排名下标树状数组上二分结果不对维护的计数存在负数检查插入和删除逻辑只对非负计数使用该二分取模结果不对add和query的取模时机不一致手动模拟小数取模统一在累加后取模并处理负数调试树状数组有个很有效的技巧设计一个debug函数把bit[1..n]全部打印出来然后手动计算每个lowbit覆盖的区间对比纸面上的模拟结果。树状数组的下标链路很短打印一两轮就能定位是方向写反还是边界写错。9.3 最佳实践与使用建议背模板前先背原理。lowbit到底在干什么update为什么向上query为什么向下这三个问题比代码本身重要。所有下标从 1 开始数组