树状数组Fenwick Tree是我在算法题和实际开发里用得最多的一种数据结构。它解决的核心问题只有一个数组频繁单点修改、频繁区间求和。和前缀和相比它支持动态更新和线段树相比它代码量小、常数小、调试成本低。这篇文章不打算只讲模板我会把树状数组的原理、手写实现、树状数组上二分、逆序对 v2 这四块完整拆开每一步都给出能直接跑的代码和判断标准。适合刚学完基础数据结构、准备刷题或者想系统复习树状数组的读者。很多人把树状数组当成一个“会背模板就行”的东西其实不是。真正容易栽跟头的不是 update 和 query 本身而是离散化、值域边界、树状数组上二分的单调性条件以及逆序对统计时的计数顺序。下面按我实际练习和踩坑的顺序重新整理一遍。1. 树状数组到底解决什么问题1.1 从动态区间求和场景出发先看一个最常见的需求。维护一个长度为 n 的数组初始值给定之后有两种操作第一种把某个位置的值加上 v第二种查询下标区间 [l, r] 的元素和。如果只用普通数组修改是 O(1) 的但区间求和需要 O(n) 遍历。如果提前预处理前缀和区间求和的复杂度变成 O(1)可一旦修改某个位置接下来所有前缀和都要更新最坏是 O(n)。当操作次数 m 和数组长度 n 都达到 10^5 甚至更大时O(n*m) 的复杂度会让程序直接超时。树状数组就是用 O(log n) 的时间同时支持单点修改和区间查询而且实现非常紧凑这也是它在竞赛和面试里出现频率很高的原因。树状数组能维护的核心信息是“可合并、可撤销”的统计量最常见的就是和。点更新、区间查询、前缀最大值、逆序对计数、第 k 小查找这些典型问题都能套进树状数组的框架。1.2 树状数组和前缀和、线段树的差异前缀和适合“一次建立、多次查询、从不修改”的静态数据。只要出现修改操作前缀和就变得麻烦。线段树理论上能处理的范围更广包括区间修改、区间最大值、最小值、区间赋值等。但线段树的代码量明显更大递归实现容易栈溢出迭代实现需要额外分配很多空间通常要开 4 倍数组长度。树状数组的空间只需要 n1写起来也更短。树状数组不能直接支持区间更新和区间查询的组合比如把 [l, r] 整体加上 v 再查询区间和这需要差分数组加两个树状数组或者干脆用线段树。所以选择依据很明确只涉及单点修改 区间求和优先用树状数组涉及区间整体修改再看线段树。1.3 核心概念lowbit树状数组的底层结构不好直接照“树”的图像理解它靠的是一个很关键的计算lowbit(x) x -x它得到的是 x 的二进制表示里最低位 1 对应的数值。比如 x 6二进制是 110lowbit(6) 2。x 8二进制是 1000lowbit(8) 8。树状数组内部用一个数组 tree 保存部分和。tree[i] 维护的是原数组从i - lowbit(i) 1到i这一段的区间和。也就是说tree[8] 存的是原数组前 8 个元素的和tree[6] 存的是原数组第 5 项到第 6 项的和。修改某个位置时要沿着下标不断加上 lowbit跳到所有包含这个位置的父节点更新它们查询前缀和时要沿着下标不断减去 lowbit把覆盖范围的区间和累加起来。很多人第一次学树状数组不知道该背 lowbit 的推导我的建议是直接记住lowbit(x) x -x这一行然后多画几个数验证。2. 手写一个能跑的树状数组2.1 环境准备与测试约定树状数组没有特殊依赖C、Java、Python 都能写。下面用 C 演示因为竞赛和面试里最常见。刷题时我一般建议用数组形式实现而不是类封装以免每次写题目都要拷贝一大段骨架。测试环境只需要支持 C11 以上不需要引入第三方库。输入输出用标准cin/cout或者快速读入都可以关键是把 update 和 query 两个函数写对。先约定数据规模数组长度 n 最大 10^5操作次数 m 最大 10^5数据范围如果是普通整数直接用 int 就能跑如果元素累加后可能超过 2^31-1就要用 long long。这个需要提前判断不要等溢出后才发现。2.2 三个核心操作树状数组的三个核心操作是更新、前缀和查询、初始化。更新操作的逻辑是从下标 pos 开始每次pos lowbit(pos)把所有覆盖到 pos 的 tree 节点都加上 delta直到 pos 超过 n。前缀和查询的逻辑是从下标 pos 开始每次pos - lowbit(pos)把 tree[pos] 累加进结果直到 pos 变成 0。初始化的方法有两种。第一种是读入原数组后对每个位置调用一次 update(i, a[i])时间复杂度 O(n log n)。第二种是直接用原数组构造 tree先让 tree[i] a[i]然后对每个 i把 tree[i] 累加到 tree[i lowbit(i)]时间复杂度 O(n)。第二种代码稍复杂一些但对于追求效率的批量场景更值得用。#include bits/stdc.h using namespace std; const int MAXN 100005; long long tree[MAXN]; int n; int lowbit(int x) { return x -x; } void update(int idx, long long delta) { while (idx n) { tree[idx] delta; idx lowbit(idx); } } long long query(int idx) { long long sum 0; while (idx 0) { sum tree[idx]; idx - lowbit(idx); } return sum; } long long rangeQuery(int l, int r) { return query(r) - query(l - 1); }注意到这里 tree 数组用了 long long。如果题目要求累加结果可能超过 int这一行能避免很多莫名其妙的 WA。2.3 最小样例验证写完模板后不要直接上大样例。我先跑一个非常小的数组人工可以手算用来确认 update 和 query 没有写反。假设 n 5初始数组 a [1, 2, 3, 4, 5]。做下面三个操作把第 3 个位置增加 2。查询 [1, 5] 的和。查询 [2, 4] 的和。手动计算初始总和 15第三个位置变成 5总和变成 17。区间 [2,4] 原先是 2 3 4 9修改后是 2 5 4 11。跑代码后update(3, 2)query(5) 应该返回 17rangeQuery(2,4) 返回 11。如果这两个结果不对不用怀疑树状数组原理先检查 lowbit 是不是x -x再检查循环方向。update 是从小下标往大下标跳query 是从大下标往小下标跳这是最容易写反的地方。这个例子跑通后再去做树状数组上二分和逆序对会踏实很多。注意不要一上来就写任务循环和高级用法。先把这一份最小模板在本地跑通确认输出和自己手算一致再往后走。3. 树状数组上二分3.1 为什么需要树状数组上二分树状数组除了维护区间和外另一个高频场景是“查找第 k 小元素”。假设有一个值域范围很大、元素动态变化的集合每个值出现的次数存在 tree 里。要查询所有已插入元素中按从小到大排序后第 k 个元素的值。最直接的方法是二分答案猜一个值 mid用 query(mid) 查询小于等于 mid 的元素个数如果小于 k 就猜大一点否则猜小一点。这个做法每次查询都要做一次 O(log n) 的 query外层二分又需要 O(log n) 次总复杂度是 O(log^2 n)。在 n 10^5、询问次数也是 10^5 的情况下log^2 n 大概是 17 * 17 289可能还能过但 n 10^6 时就会吃力。树状数组上二分可以把这个过程压缩到单次 O(log n)原理是利用树状数组 tree[i] 天然保存区间和这一特性从高位到低位逐步逼近答案。3.2 倍增逼近的原理树状数组的 tree[pos] 保存的是下标[pos - lowbit(pos) 1, pos]的和。如果我们在奇偶性上做文章可以从一个很大的步长开始比如从1 LOG递减判断当前累计的区间和是否仍然小于 k如果是就把当前位置右移对应步长同时累计这个区间的和。这个思路和倍增 LCA 很像。核心不变式是当前已经确认“前缀位置 cur 之前的元素总数”为cnt并且cnt k。每一步尝试把 cur 向右移动一段长度 step如果移动后cnt tree[cur step]仍然小于 k就说明目标位置还在更右边这个 step 是安全的可以加上。从大到小枚举 step 的好处是每个二进制位只判断一次最终得到的位置就是满足“前缀和小于 k 的最大位置”加 1 就是第 k 小元素所在的下标。要注意这个做法要求 tree 中存的是非负值也就是每个离散化后的坐标出现的次数不能小于 0。因为只有非负前缀和才是单调不减的倍增的贪心移动才不会出错。如果数据里有负数需要先偏移到正数域。3.3 代码实现下面是标准的树状数组上二分查找第 k 小位置的代码。LOG可以取__lg(n) 1也可以直接取 20 或 31但要注意不要越界访问 tree 数组。int findKth(long long k) { int idx 0; int maxPow 1; while (maxPow n) maxPow 1; for (int step maxPow 1; step 0; step 1) { int nxt idx step; if (nxt n tree[nxt] k) { idx nxt; k - tree[nxt]; } } return idx 1; }这里的tree数组存的是每个离散化坐标上的元素数量。函数返回满足query(pos - 1) k query(pos)的最小 pos。我建议自测一下这个例子假设插入元素 [1, 1, 2, 3, 5]也就是离散化后坐标 1 有 2 个坐标 2 有 1 个坐标 3 有 1 个坐标 5 有 1 个。此时查找第 4 小的元素预期结果是 3。逻辑上前 3 个元素是 1、1、2第 4 个是 3。如果代码返回 3说明二分思路正确。如果返回 2说明移动条件写成了 k导致把等于 k 的情况提前移动了。3.4 适用范围和注意事项树状数组上二分并不是万能的。它只适合查找“前缀和函数单调”的统计问题常见的是频次分布、可重复元素的第 k 小。如果你的数据带有删除操作且删除会导致负数就不能直接用这种倍增找第 k 小。此外树状数组上二分得到的答案是离散化后的坐标不是原值。把原值映射到离散坐标之后还要根据坐标反向映射回原值。这个映射关系经常被忽略。实测中还有一个细节当 k 大于当前总元素个数时findKth 会返回 n1需要提前判断。我一般会在插入和删除操作后维护一个 total 变量调用 findKth 前先检查k total避免越界或返回错误。4. 逆序对 v2用树状数组实现4.1 逆序对定义和暴力做法逆序对是指数组里满足i j且a[i] a[j]的下标对(i, j)数量。比如数组 [5, 2, 6, 1]逆序对有 (5,2)、(5,1)、(2,1)、(6,1)总共 4 个。暴力做法是双重循环O(n^2)。当 n 达到 10^5 时10^10 次比较会超时。所以需要用数据结构优化。“逆序对 v2”这里指的就是基于树状数组的动态统计版本一边遍历原数组一边把当前元素插入树状数组同时查询已经插入的元素里有多少个比当前元素大。这样每个元素只需要一次 update 和一次 query总体复杂度 O(n log n)。4.2 为什么要离散化如果数组元素值域很大比如 10^9那么树状数组无法直接开这么大的数组。解决办法是把所有出现的值先收集起来排序去重得到每个值对应的排名这个步骤叫离散化。离散化之后原本的值范围被压缩到 1 到 mm 最多是 n。我们用离散化后的排名作为树状数组的下标每个位置存的是“该排名出现了几次”。离散化本身要排序时间复杂度 O(n log n)和后面的统计操作相加整体还是 O(n log n)。4.3 从左到右扫描并统计核心逻辑是维护一个树状数组下标是离散化后的值值存的是已经扫描过的元素中该值的出现次数。当遍历到第 i 个元素 x 时查询所有已经插入的元素中小于等于 x 的数量cnt_le。注意这里是等于也要算进去因为逆序对要求严格大于。当前已经插入的元素总数是 i因为遍历下标从 0 开始所以已经插入了 i 个。那么已经插入的元素中严格大于 x 的数量就是i - cnt_le。把这个数量累加到答案。再把当前元素离散化后的排名插入树状数组也就是该排名的出现次数加 1。这里容易犯的错误是查询方向。树状数组 query(x) 返回的是前缀和也就是小于等于 x 的数量。如果要求严格小于就要写成 query(x - 1)而不是 query(x)。逆序对需要严格大于所以必须先算小于等于再用总数减。如果数组有重复元素离散化时相同的值必须映射到同一个排名才可以正确统计等于的情况。4.4 完整代码#include bits/stdc.h using namespace std; const int MAXN 100005; long long tree[MAXN]; int n; vectorint vals; int lowbit(int x) { return x -x; } void update(int idx, int delta) { while (idx n) { tree[idx] delta; idx lowbit(idx); } } long long query(int idx) { long long res 0; while (idx 0) { res tree[idx]; idx - lowbit(idx); } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n; vectorint a(n); for (int i 0; i n; i) { cin a[i]; vals.push_back(a[i]); } sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); long long ans 0; for (int i 0; i n; i) { int rank lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin() 1; long long cntLessEqual query(rank); ans i - cntLessEqual; update(rank, 1); } cout ans \n; return 0; }这里 tree 的下标上限是去重后的大小 maxRank不是原始 n。如果原始数组所有元素都一样大maxRank 会是 1树状数组只需要很小的空间。为了代码简单我直接让数组开 MAXN循环里用while (idx ::n)可能会导致越界更新到 n 以外的位置虽然一般不会报错但最好把 update 的上限改成maxRank。更规范的做法是保存离散化后的数组长度int m vals.size(); // update 中 while (idx m) // query 中 idx 0这样才是一个严格适配值域空间的树状数组。4.5 时间复杂度和空间占用整个流程分两块离散化排序 O(n log n)统计阶段每个元素一次查询一次更新各 O(log n)总复杂度 O(n log n)。空间上树状数组开 m1m 是去重后的元素个数。原始数组和离散化使用的 vals 也各占 O(n)。和其他数据结构相比树状数组已经是同复杂度问题里内存占用最小的方案之一。实测时要注意 n 10^5 时答案可能上界是 n*(n-1)/2约 5*10^9需要 long long。如果答案用 int统计到一半就可能溢出变成负数排查起来非常隐蔽。5. 这 4 种高频报错和排查顺序5.1 数组越界和空间开小树状数组最容易踩的坑是把 tree 数组开成 n但更新时idx lowbit(idx)可能跳到比 n 还大的位置。虽然很多环境不会立刻崩溃但会覆盖到旁边的变量导致结果随机变化。排查方式确认 tree 大小至少为 n1并把 update 的上限改成离散化后的实际大小 m。可以用valgrind或 AddressSanitizer 在本地跑一遍如果用了-fsanitizeaddress越界会在报错信息里直接显示。5.2 更新和查询循环写反update 的循环是idx n每次加上 lowbitquery 的循环是idx 0每次减去 lowbit。很多人会把两者颠倒结果就是修改没有反映到查询结果上。排查方式用最小样例手算一次对比 query 返回的前缀和。如果 query(1) 正常但 query(3) 少了一段多半是 tree 节点没被正确更新。5.3 值域为负或过大没有离散化树状数组的下标必须从 1 开始。如果原始数据存在负数直接把它当成下标会越界如果值域达到 10^9开这么大的数组也不现实。排查方式观察数据范围。只要值域大于 10^6 或者存在负数就优先做离散化。离散化时记得去重并映射到 1 到 m代码里所有查询和更新都用映射后的排名。5.4 树状数组上二分结果不对结果不对通常有两个原因。第一tree 中存的不是频次而是其他意义的值破坏了前缀单调性。第二移动条件写成了tree[nxt] k导致在“等于 k”的情况下多移动了一段。排查方式先构造一个只包含频次的简单样例比如 [1, 2, 2, 3]分别查第 1、2、3、4 小看输出是否依次是 1、2、2、3。如果第 2 小输出 1说明移动条件有问题如果输出 3说明更新时下标偏移有问题。注意树状数组上二分的正确性依赖所有位置上的值非负。如果插入过程中有删除操作且允许删除不存在的元素会破坏这个前提。6. 实战建议和扩展方向6.1 新手建议如果是第一次学树状数组我的建议是把模板背到“不用想就能写”的程度尤其是 lowbit、update、query 这三行。之后再用小样例验证不要直接去做很难的题。先练三类题型单点更新 区间查询。求逆序对。求第 k 小元素。这三个问题能覆盖树状数组 80% 的使用场景。每道题都先写暴力再写树状数组版本对比结果能更快理解树状数组到底优化了什么。6.2 进阶题目方向树状数组还能处理一些更复杂的问题比如带修改的区间第 k 小、二维树状数组、树状数组维护前缀最大值、树状数组配合离线询问解决“区间内不同数字的数量”等。这些题目核心原理不变但要注意“树状数组上二分”只能解决值域是静态的“所有插入竞争同一棵树”的场景。如果问题需要支持删除和插入最好配合哈希表维护频次删除时更新对应位置为 -1然后仍然保证所有值非负才能继续用二分查找第 k 小。6.3 什么时候不要用树状数组树状数组不是万能的。如果涉及区间整体更新、区间查询最大值、区间查询最小值树状数组会写得很别扭通常需要拆成多个结构或者直接上线段树。另外如果问题允许离线且答案只是区间和可以先用前缀和把所有查询预处理不一定需要树状数组。树状数组的适用边界是存在动态更新且只关心可合并的前缀信息。我个人更建议先把单点更新、前缀和查询和逆序对这三个模板跑稳再碰树状数组上二分。踩过几次坑之后会发现很多问题不是数据结构本身难而是空间上限、值域离散化和更新顺序没想清楚。这几个点想明白了树状数组基本就不会再出大问题。