树状数组原理与实战：从lowbit到区间更新、第k小与逆序对

树状数组是非常值得花时间彻底讲清楚的一个数据结构。它用极小的代码量解决了“单点修改 前缀和查询”这类高频问题而且很容易扩展到区间更新、动态第 k 小、逆序对计数等经典场景。很多算法题不会直接告诉你“这题用树状数组”但当你发现题目需要反复修改某个位置的值、查询某段区间的和或频次时树状数组往往是最短、最快的那把锤子。这篇内容不是只列模板而是尽量把原理讲透。我们从lowbit开始先完成最基础的单点修改和前缀和查询然后引入差分树状数组处理区间更新和区间查询接着重点分析“树状数组上二分”也就是如何在权值树状数组上快速找到第 k 小最后给出逆序对 v2 的树状数组优化写法并补充常见的越界、溢出、离散化问题和工程化建议。看完全文你可以直接把模板用在力扣、洛谷或者面试题里。这套内容适合已经能熟练写数组循环、了解二分查找的读者。如果你之前只会用线段树也可以借这篇补上常数更小、代码更短的方案。同时要明确一个边界树状数组不适合区间取最值、不适合复杂的区间懒标记。它擅长的是频次统计、求和与排序类问题把这几个场景用好性价比非常高。1. 树状数组核心能力速览项目说明数据结构类型前缀和 / 频次统计类数据结构核心操作复杂度单点修改 O(log n)前缀和查询 O(log n)区间和 O(log n)空间复杂度O(n)只需要一个一维数组支持操作单点修改、前缀和查询、区间和、区间更新配合差分、第 k 小树状数组上二分、逆序对计数典型应用逆序对、权值统计、动态前缀和、离线算法中的频次维护对比线段树代码更短、常数更小、更容易调试不支持区间最值不支持复杂懒标记常用语言C、Java、Python 均可实现核心逻辑一致从表格可以看出树状数组并不是一个“大而全”的数据结构。它最有价值的场景是频繁单点修改 频繁前缀查询这两步操作都可以稳定在 O(log n)。相比线段树树状数组代码只有几行出错概率更低相比前缀和数组它不需要因为修改而整体重建数组。所以我的建议是遇到区间求和、频次统计、动态排名这类问题先考虑树状数组只有遇到区间最大值、区间最小值或者需要打复杂懒标记时再换线段树。这样能明显减少实现时间和调试成本。2. 适用场景与不适用场景树状数组适合解决的问题可以归纳成三类。第一类是单点修改、区间查询。典型例子是维护一个数组支持把某个下标的值增加 x同时查询 [l, r] 的和。前缀和数组在修改时是 O(n)树状数组把修改和查询都降到 O(log n)在数据量大的时候优势非常明显。第二类是权值统计和排名问题。把数组里的每个值作为下标用树状数组统计每个数值出现的次数。比如求逆序对就是边扫描边统计已经出现的元素个数比如动态插入若干数字后查询第 k 小就可以用树状数组上二分。这类问题本质上是把普通数组的计数操作变成支持单点增加和前缀频次查询。第三类是离线算法中的频次维护。很多二维偏序、离线排序、扫描线问题最终都会化成“按某个维度排序再用树状数组维护另一个维度的增量”。这也是树状数组在算法竞赛中出现频率极高的原因之一。不适用场景也很明确。如果你需要查询区间最大值或最小值树状数组很难处理因为树状数组的节点存的是区间和无法快速合并 max/min 信息。如果你需要区间整体赋值比如把 [l, r] 全部变成 v并且之后要快速查询树状数组也不合适这需要线段树的懒标记或珂朵莉树。总之求和与计数优先树状数组最值与复杂区间操作优先线段树。3. lowbit 与原理解读树状数组的核心只有一行公式lowbit(x) x (-x)。这个值表示 x 的二进制表示中最低位的 1 以及它后面的 0 所组成的数。比如lowbit(6)6 的二进制是 110最低位的 1 在第 2 位所以lowbit(6) 2lowbit(8)8 的二进制是 1000所以lowbit(8) 8。为什么树状数组依赖lowbit因为树状数组的一个关键设计是下标 i 负责存储区间[i - lowbit(i) 1, i]的和。也就是说tree[i]不是简单的第 i 个数而是从某个左端点累加到 i 的区间和。左端点的位置由lowbit(i)决定。举几个例子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查询前缀和时只需要向下减lowbit。两者的路径长度都是 O(log n)。理解lowbit有一个很有效的办法在纸上画出二进制。更新时下标从当前节点不断加上自己的lowbit直到超过 n查询时下标从当前节点不断减去自己的lowbit直到变成 0。这个过程不依赖递归循环就能写完这也是树状数组代码简洁的根本原因。理解了lowbit后续的所有操作都会变得非常自然。你不需要背代码只需要记住两句话修改往右走查询往左走。4. 基础操作单点修改、前缀和查询、区间和先给出最基础的三个函数这里用 C 实现。假设树状数组是全局数组tree大小为MAXN所有操作下标从 1 开始。#include bits/stdc.h using namespace std; const int MAXN 100005; int tree[MAXN]; int n; // 单点修改把下标 pos 的值增加 delta void add(int pos, int delta) { for (int i pos; i n; i i (-i)) { tree[i] delta; } } // 前缀和查询求 [1, pos] 的和 int sum(int pos) { int res 0; for (int i pos; i 0; i - i (-i)) { res tree[i]; } return res; } // 区间和查询求 [l, r] 的和 int rangeSum(int l, int r) { return sum(r) - sum(l - 1); }add函数的更新路径很典型。比如修改下标 3那么tree[3]、tree[4]、tree[8]等节点都要更新因为 3 这个位置被这些区间覆盖。i (i -i)正好沿着覆盖区间向上跳。sum则相反查询下标 7 的时候会累加tree[7]、tree[6]、tree[4]恰好覆盖 [7,7]、[5,6]、[1,4]完整组成 [1,7]。下面用一个例子验证。假设初始数组是[3, 1, 4, 1, 5]我们逐个addint main() { n 5; for (int i 1; i 5; i) { // 假设 a[i] 依次为 3,1,4,1,5 int a[] {0, 3, 1, 4, 1, 5}; add(i, a[i]); } cout rangeSum(2, 4) endl; // 期望输出 1416 add(3, 2); // 下标 3 增加 2数组变成 [3,1,6,1,5] cout rangeSum(2, 4) endl; // 期望输出 1618 return 0; }第一次rangeSum(2, 4)输出 6第二次在把下标 3 的值加 2 后区间 [2,4] 的和变成 8。这个基本流程可以验证树状数组是否正确。这里还有一个常见的初始化优化。如果一开始有一个完整的数组并且要批量建树不需要对每个元素单独调用add那样是 O(n log n)。可以先直接把tree[i] a[i]然后从下标 1 开始向上累加void build() { for (int i 1; i n; i) { tree[i] a[i]; int j i (i -i); if (j n) { tree[j] tree[i]; } } }build的时间复杂度是 O(n)。在小数据量下看不出区别但在 n 超过 1e6 时O(n log n) 和 O(n) 的差距会很可观。5. 区间更新与区间查询差分树状数组基础树状数组只能做“单点修改 区间查询”。如果题目要求“把 [l, r] 的所有元素都增加 v”然后再查询某个区间的和基础版就不好直接处理了但可以借助差分思想转成单点修改。先看一个简化问题区间加单点查询。定义差分数组diff[i] a[i] - a[i-1]那么对原数组区间 [l, r] 加上 v等价于diff[l] vdiff[r1] - v。当需要查询位置 pos 的值时只需要统计diff[1] diff[2] ... diff[pos]也就是原数组的前缀和。用树状数组维护差分数组就能把区间加转成两次单点修改把单点查询转成一次前缀和查询。代码如下void rangeAdd(int l, int r, int v) { add(l, v); add(r 1, -v); } int pointQuery(int pos) { return sum(pos); }如果问题升级为区间加、区间查询我们需要维护两个树状数组。原理是展开区间和公式对原数组做差分得到diff则前缀和[ \sum_{i1}^{x} a_i \sum_{i1}^{x} \sum_{j1}^{i} diff_j (x1) \cdot \sum_{j1}^{x} diff_j - \sum_{j1}^{x} j \cdot diff_j ]所以只要用树状数组维护diff[i]和i * diff[i]两个东西就能在 O(log n) 内完成区间加和区间查询。模板如下long long bit1[MAXN], bit2[MAXN]; void add(long long bit[], int pos, long long v) { for (int i pos; i n; i i (-i)) bit[i] v; } long long sum(long long bit[], int pos) { long long res 0; for (int i pos; i 0; i - i (-i)) res bit[i]; return res; } void rangeAdd(int l, int r, long long v) { add(bit1, l, v); add(bit1, r 1, -v); add(bit2, l, l * v); add(bit2, r 1, -(r 1) * v); } 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); }这里两个树状数组的更新逻辑必须保持一致。初学的时候比较容易漏掉bit2的更新导致查询结果错乱。建议先用小数组手动模拟一遍再套到题目模板里。需要提醒的是差分树状数组适合区间加这种线性增量操作它不能解决区间赋值也不能解决区间最大值、最小值问题。遇到区间最值请直接考虑线段树。6. 树状数组上二分解决“第 k 小”问题树状数组最精彩的进阶操作是“树状数组上二分”。它解决的问题是在一个支持单点修改的权值数组里快速找到前缀和第一次达到 k 的位置也就是动态集合中的第 k 小。先说明什么是权值树状数组。把每个可能出现的数值看作下标tree[i]表示数值 i 出现的次数。插入一个数 x就执行add(x, 1)删除一个数 x就执行add(x, -1)。要统计小于等于 x 的数有多少个就执行sum(x)。这样树状数组就变成了一个支持动态插入、删除、排名的数据结构。在权值树状数组上找第 k 小看起来可以用二分下标 查询前缀和来做复杂度 O(log^2 n)。但利用树状数组的结构我们可以做到 O(log n)。核心思想是从二进制最高位开始尝试跳到一个尽可能大的位置同时保证跳过去之后的前缀频次仍然小于 k。标准写法如下// 权值树状数组值域为 1..n int findKth(int k) { int pos 0; for (int step 1 20; step; step 1) { int nxt pos step; if (nxt n tree[nxt] k) { pos nxt; k - tree[nxt]; } } return pos 1; }这里的tree[nxt]为什么可以直接和 k 比较因为树状数组在倍增跳的过程中nxt恰好是pos step而tree[nxt]保存的区间是[nxt - lowbit(nxt) 1, nxt]。当step取的是lowbit(step)时nxt正好是某个连续块的位置tree[nxt]就是当前尝试跳过的这个块内的累计频次。需要注意findKth(k)要求1 k 总共插入的元素个数。如果k大于总频次函数会返回n 1调用前要先判断一下。这里的1 20是最高位的初始步长具体值要根据 n 的上限决定比如 n 最大 1e5初始步长取1 17就够了取大一点不影响正确性只要保证step从大于 n 的最高二进制位往下减就行。下面用一个例子验证。假设当前集合是{1, 3, 3, 5, 7}统计频次后得到数值1234567频次1020101执行findKth(4)时应该返回第 4 小的数也就是 5。过程大致是先跳过 1 和 3累计频次 3然后跳到 5发现加上 5 的频次后达到 4所以返回 5。用代码跑一遍结果一致。树状数组上二分最常见的应用是动态维护有序集合比如每次插入一个新数、删除一个数然后询问当前第 k 大或第 k 小。另一个常见场景是逆序对问题的加强版如果题目还要支持“删除某个数后查询第 k 小”普通排序就不够用了树状数组上二分可以稳定解决。7. 逆序对 v2树状数组的经典进阶逆序对的定义是对于数组a如果i j且a[i] a[j]那么(i, j)是一个逆序对。求逆序对数量最朴素的做法是双重循环O(n^2)归并排序可以做到 O(n log n)树状数组同样可以做到 O(n log n)而且代码更短扩展性更强。经典树状数组求逆序对的方法是从右往左扫描数组每扫到一个数x先查询当前已经插入的、小于等于x-1的数有多少个这些数都在 x 的右侧且比 x 小因此与 x 构成逆序对然后把x插入权值树状数组。int a[MAXN]; int sorted[MAXN]; // 用于离散化 int n; int getRank(int val) { return lower_bound(sorted 1, sorted n 1, val) - sorted; } long long solve() { // 复制并排序用于离散化 for (int i 1; i n; i) sorted[i] a[i]; sort(sorted 1, sorted n 1); long long ans 0; for (int i n; i 1; i--) { int rk getRank(a[i]); ans sum(rk - 1); // 已经插入的且值小于 a[i] 的个数 add(rk, 1); // 当前值插入树状数组 } return ans; }为什么叫“逆序对 v2”因为在初学版本中很多人会直接开一个大小等于值域的数组假设数值范围是 1 到 1e9那数组根本开不下。通过离散化我们只关心数值之间的相对大小把每个原始值映射为排序后的下标然后把树状数组压缩到 O(n) 大小。这一步是树状数组处理大规模逆序对的常见优化也是从模板题进入实战题的分水岭。离散化之后的逆序对计算本质上就是维护一个动态频次表。从右往左扫描时已经插入的元素都在当前元素的右侧sum(rk - 1)统计的是右侧小于当前元素的个数。如果你习惯从左往右扫描也可以用ans (i - 1) - sum(rk)意思是当前左侧元素中大于当前元素的个数两种方向等价。这里有必要强调两个容易出错的地方。第一逆序对数量可能很大n 的规模到 1e5 时最坏情况逆序对数量接近 n*(n-1)/2会超过 int 范围必须使用 long long。第二如果数组中有重复元素用sum(rk - 1)可以避免把相等元素计入逆序对符合逆序对的严格大于定义。如果题目需要进一步支持“删除一个数后查询第 k 小”可以把逆序对 v2 和树状数组上二分结合起来。先用离散化后的权值树状数组维护全部频次删除时执行add(rk, -1)查询第 k 小时用findKth(k)。这样一套代码就能覆盖动态排名和逆序对两大类问题。8. 性能观察与参数选择树状数组的时间复杂度分析很稳定。单点修改 O(log n)前缀和查询 O(log n)区间和查询是两次前缀和相减也是 O(log n)。建树时逐个插入是 O(n log n)用线性建树可以到 O(n)。树状数组上二分是 O(log n)不是 O(log^2 n)这是它比“二分答案 前缀和查询”更快的原因。空间上只需要一个 O(n) 的数组。与线段树相比线段树通常要开 4n 的节点树状数组只开 n2 就够了。在内存紧张或需要维护多个维度的题目中这个优势会很明显。比如同时维护差分数组和带有权参数的数组也只需要两个 O(n) 数组。实际运行时间受到语言和常数影响。C 的树状数组通常非常快Python 在 n 达到 1e6 时会偏慢因为循环和函数调用开销较大此时可以考虑用 PyPy或者使用列表展开写法来减少调用层数。具体时间不做定值预测但复杂度分析是确定的O(n log n) 的算法处理 1e5 级别数据通常足够处理 1e6 级别数据需要关注常数和内存。选择参数时要关注三个点数组长度至少开n 2因为r 1这类更新可能访问到n 1。用int还是long long取决于累加和是否可能溢出。求和、逆序对、区间更新都必须仔细考虑。树状数组上二分的初始步长要覆盖整个值域。如果n是 1e5初始步长1 17就够稳妥起见可以直接从1 20或更大的二进制位开始。降低出错概率的方法也很简单把add和sum封装成函数统一使用int或long long参数在每次修改和查询前确认数组下标从 1 开始而不是从 0 开始。大量树状数组的 bug 都来自“下标从 0 开始”或“越界一位”这两个问题。9. 常见问题与排查方法问题现象可能原因排查方式解决方案所有前缀和结果为 0下标从 0 开始打印lowbit和tree路径所有操作下标从 1 开始更新后查询结果不对更新路径漏加或重复加小数组手动模拟一次检查i i (-i)路径数组越界pos等于 n 时更新到 n1打印边界数组开大开n2区间更新后单点查询值不对r1位置没有减掉检查差分树状数组逻辑确认rangeAdd(l, r, v)两个add都执行逆序对结果负数未正确处理重复元素检查离散化后的rk用sum(rk-1)而不是sum(rk)逆序对结果溢出int 不够用打印ans估算改用long longfindKth返回 n1k 大于总频次调用前检查sum(n)先判断k sum(n)树状数组上二分结果错误初始步长没有覆盖值域输出每个step的尝试结果从大于 n 的二进制位开始递减输入很大但程序很慢使用 O(n log n) 建树或 Python 函数调用过多压测时间改用线性建树或用 PyPy排查树状数组问题时最好的方法不是盯代码而是构造一个长度为 4 或 8 的小数组把tree数组的覆盖区间画出来逐步执行add和sum。只要lowbit计算正确、下标从 1 开始、范围判断正确大多数错误都能很快定位。10. 最佳实践与使用建议树状数组适合整理成固定模板。在 C 里可以封装成一个类避免全局变量污染在 Python 里可以封装成类或者直接用闭包维护内部数组。下面给出一份 C 封装示例适合作为比赛或工程基础模板class Fenwick { int n; vectorint tree; public: Fenwick(int n) : n(n), tree(n 2, 0) {} void add(int pos, int delta) { for (int i pos; i n; i i (-i)) { tree[i] delta; } } int sum(int pos) { int res 0; for (int i pos; i 0; i - i (-i)) { res tree[i]; } return res; } int rangeSum(int l, int r) { return sum(r) - sum(l - 1); } int findKth(int k) { int pos 0; for (int step 1 20; step; step 1) { int nxt pos step; if (nxt n tree[nxt] k) { pos nxt; k - tree[nxt]; } } return pos 1; } };工程化使用时有四条建议。第一初始化时优先使用线性建树。如果题目会一次性给完所有数组先复制一份数组用线性建树把 O(n log n) 降到 O(n)。这在多组测试数据时能明显节省时间。第二每次写树状数组前先写一个lowbit的小工具或注释比如lowbit(x) x (-x)避免在循环里写错。循环条件也可以统一写成i n和i 0不要随手改成别的形式。第三测试阶段先用小样例验证再跑大数据。小样例可以用暴力法双循环对拍确认无误后再提交。尤其对于逆序对、区间更新这类题对拍能快速暴露边界错误。第四如果在 Python 或 Java 中实现不要频繁在类方法里访问全局数组可以把tree作为局部变量传入函数减少属性查找开销。Python 的list和 PyPy 配合时树状数组处理 1e5 级别数据是可行的。树状数组虽然代码短但抽象程度并不低。它把一组相互重叠的区间组织成树形关系理解了这个结构才能真正灵活运用。建议不要只背模板而是自己画一遍下标 1 到 8 的覆盖关系然后手写add和sum直到能不假思索地写出来。11. 总结与下一步树状数组最值得掌握的是三个能力一是用lowbit理解区间覆盖和更新路径二是把差分思想接入树状数组解决区间更新三是在权值树状数组上做二分解决动态第 k 小问题。这三个能力串联起来就能解决一大类“单点修改 前缀查询”的算法题。如果你刚开始学先跑通基础模板验证单点修改和区间和如果你已经在刷题优先把逆序对 v2 和树状数组上二分练熟因为它们几乎是树状数组实战题的必背套路。最容易踩的坑依然是下标越界、long long 溢出以及findKth的步长没有覆盖值域。下一步可以继续扩展的方向包括二维树状数组、离线 CDQ 分治、树状数组优化动态规划以及在 BIT 上维护贪心策略等。树状数组虽然基础但它几乎是所有高级偏序算法的地基值得反复打磨。建议把这篇文章里的模板收藏备用刷题遇到“修改 查询”的结构时直接拿出来对照使用。