简介：面向算法竞赛初学者的树状数组（Binary Indexed Tree）学习与模板资源，精选洛谷经典例题 P1428“小鱼比可爱”，同时提供可直接套用的 C/C++ 模板与编译好的可执行程序。树状数组适合处理动态区间求和、前缀和、区间最值等高频操作，在竞赛中常用于替代线段树以节省内存和编码量，是必备基础数据结构之一。压缩包共6个文件，其中 cpp/c 为源码与模板实现，exe 为可直接运行的程序，方便与输出结果（out 文件）对照验证，整体仅452KB，非常轻量。内容从单点更新、区间查询到时间复杂度分析均有对应实现，读者可结合洛谷题目逐步理解 BIT 的构造、更新和求和原理；模板代码简洁，既可学习也可作为后续做题的基础框架。目前已有1412人学习下载，适合正在刷洛谷树状数组专题、准备算法竞赛或需要快速掌握 BIT 的初学者使用。

1. 树状数组模板和入门题源码：这份压缩包值不值得拆开看

树状数组的模板网上随处可见，但真正拿到手能直接过题、不踩边界坑的并不多。我拆过的这份树状数组.zip里，核心文件是一个模板.cpp，外加两份《小鱼比可爱》的 C 源码、对应的.exe和一个调试残留的gmon.out，正好覆盖了“抄模板 → 套题目 → 对拍验证 → 清理调试产物”的完整链路。需要提前说一句：这份资源的摘要描述把树状数组和线段树当成同一个东西，这俩只是都能做区间维护，底层思想和代码结构完全不同，下面会专门讲清区别。如果你刚开始刷 OJ、需要一份能改改就用的树状数组模板，或者想找一道经典入门题看完整解法，这份压缩包值得下；如果你期望它像高级数据结构的封装库那样可以直接调接口，那要失望了，它是一份很朴素的竞赛选手手写代码。

2. 树状数组原理：lowbit 与二进制索引决定了一切

2.1 用数组模拟树：每个节点到底存了哪一段的和

树状数组的核心不是一棵显式的二叉树，而是一个普通数组tree[]，靠下标二进制里的最低位 1 来隐式地划分区间。设lowbit(i)表示i的二进制表示中最低位的 1 所对应的值，那么tree[i]保存的是原数组区间[i - lowbit(i) + 1, i]的累积和。例如lowbit(6) = 2，所以tree[6]只负责[5, 6]这段；lowbit(4) = 4，tree[4]负责[1, 4]。

这个划分方式和线段树完全不同：线段树是一棵真正递归定义的完全二叉树，每个节点的子节点边界靠区间中点切分；树状数组则是站在某个下标上，用i + lowbit(i)找到父节点，用i - lowbit(i)找到下一个需要累加的兄弟区间。理解这一点，后面所有代码就都顺了。

举一个n = 8的例子，把下标、lowbit 和管辖区间列出来，代码调试时对照这张表非常直观：

注意看，i的管辖区间长度恰好等于lowbit(i)，而更新时每次跳到的位置是当前下标加上它的lowbit。这套跳转规则是树状数组唯一需要记住的东西。

2.2 lowbit 的写法：补码与位运算

C/C++ 里lowbit的标准写法只有一行：

int lowbit(int x) { return x & (-x); }

逻辑说明：在补码表示下，-x等于~x + 1。对任意正整数x，x & (-x)的结果恰好保留最低位的那个 1，其余位全部置 0。例如x = 6，二进制是110，-6的补码是010，按位与得到010，即十进制的 2，正好是lowbit(6)。

参数说明：传入的是树状数组的下标，要求大于 0。如果下标是 0，lowbit(0) = 0，更新循环会永远停在原地，这是最常见的死循环来源。实际做题时凡是读入的值可能为 0（比如统计比当前数小的个数），都要先做偏移，把所有数整体平移为正，再进入树状数组。

2.3 单点更新与前缀查询：对称的二进制跳跃

更新和查询是树状数组的两条主路径。更新从叶子往上走，查询从当前点往下拆，两条路径都依赖 lowbit 移动下标：

void update(int i, int delta) { while (i <= n) { tree[i] += delta; i += lowbit(i); } } int query(int i) { int sum = 0; while (i > 0) { sum += tree[i]; i -= lowbit(i); } return sum; }

update的含义是：原数组第i个位置增加了delta，所有管辖范围包含i的树节点都要同步加delta。路径就是i -> i + lowbit(i) -> ...，最坏情况下要更新log n层。以i = 3为例，更新路径是 3、4、8，跳转路径在上面的表里能直接查到。

query的含义是：求原数组[1, i]的前缀和，它从i开始，每次减掉lowbit(i)，把沿途节点累加。比如query(7)会依次加tree[7]、tree[6]、tree[4]，分别对应当前管理区间[7,7]、[5,6]、[1,4]，拼起来正好是[1,7]。

有人会问：区间[l, r]的和怎么办？正确答案是query(r) - query(l - 1)，先算两个前缀和再相减。那份资源摘要里提到的“从 l 和 r 分别向上遍历到根节点，把两个节点的值相加”是错误写法，树状数组不这样求区间和。只要按照query(r) - query(l - 1)来写，逻辑上就和一维前缀和一致了。

时间复杂度方面，单点更新和前缀查询都是O(log n)，但常数比线段树小很多。因为每次循环只是简单的加减和位运算，没有递归、没有区间懒标记，所以同样的题目规模，树状数组往往更快，代码也更短。

3. 压缩包拆解：模板.cpp、两份 C 源码、.exe 与 gmon.out 各有什么价值

3.1 文件清单与用途

把压缩包解开后，我按使用价值把文件分成了三类。下面这张表基本说明了一切：

gmon.out是程序带-pg参数编译运行后生成的 profiling 文件，里面是二进制性能采样数据。它没有可读性，也不是项目的一部分，纯粹是打包时忘了清理的残留物。看到它不需要慌，忽略即可。

3.2 模板.cpp 的可复用骨架

把模板打开，整体结构一般是这样：

#include <bits/stdc++.h> using namespace std; const int MAXN = 500000 + 5; int tree[MAXN]; int n; int lowbit(int x) { return x & (-x); } void update(int i, int delta) { while (i <= n) { tree[i] += delta; i += lowbit(i); } } int query(int i) { int res = 0; while (i > 0) { res += tree[i]; i -= lowbit(i); } return res; } int main() { // 根据题目读入 n 和操作 return 0; }

逻辑说明：全局数组默认清零，省掉显式初始化。MAXN决定了树状数组能覆盖的最大下标，实际使用时有三个需要改的地方：MAXN根据题目数据范围调整；如果n是全局变量需要读入后赋值；如果求区间和的数据可能超过int，把tree改成long long。这个模板只支持单点更新和前缀查询，遇到区间修改的题需要在update循环里加方向判断，或者改用差分思路。

3.3 两份同名 C 源码怎么看

压缩包里出现了两个非常相似的文件名，大概率一个是暴力解法，一个是树状数组解法。我把它们并排打开后，最直观的观察方式是直接看主循环：暴力版一般是双重for遍历，树状数组版则是update和query交替调用。如果你拿到压缩包后发现两份都是树状数组写法，那可能是一个用while循环手动实现，另一个用for循环实现，差别不影响算法。

看这种同名文件的时候，我的习惯是先做一次文本对比，把除变量名外的差异高亮出来。重点看三个位置：lowbit的写法是否一致、update循环的终止条件是不是写错成i > 0、建树过程是在读入时逐点update还是先拿原数组重建。这三个位置几乎覆盖了树状数组题目的全部低级错误来源。

4. 《小鱼比可爱》实战：从暴力到树状数组的完整改造

4.1 题目到底在问什么

这道入门题的意思是：给定长度为n的数组，对每个位置i，统计1到i-1中有多少个元素的值小于当前元素。数据范围一上来，暴力就废了：如果n是几十万，双重循环直接超时，这时必须把“统计左侧比自己小的元素个数”转换成“按值域动态插入和查询前缀和”。

处理方式是边读入边操作：读到当前值x时，先查询目前已经插入的元素中有多少小于x的，再把当前值插入树状数组。查询结果就是题目要的答案，单个元素的处理复杂度是O(log V)，V是值域范围。

4.2 暴力解法与树状数组解法对照

暴力版本的核心循环大概是这样的：

for (int i = 0; i < n; i++) { int cnt = 0; for (int j = 0; j < i; j++) { if (a[j] < a[i]) cnt++; } printf("%d%c", cnt, i == n - 1 ? '\n' : ' '); }

这份代码没有任何数据结构的成分，只是在模拟题意。它能应付n <= 1000的小数据，但实际数据一大就翻车，属于典型的“能跑但过不了”的版本。

树状数组版本把内层循环优化成了按值域的两次操作：

#include <stdio.h> #include <string.h> #define MAXV 1000000 int tree[MAXV + 5]; int lowbit(int x) { return x & (-x); } void update(int i, int delta) { while (i <= MAXV) { tree[i] += delta; i += lowbit(i); } } int query(int i) { int res = 0; while (i > 0) { res += tree[i]; i -= lowbit(i); } return res; } int main() { int n, x; scanf("%d", &n); memset(tree, 0, sizeof(tree)); for (int i = 0; i < n; i++) { scanf("%d", &x); printf("%d%c", query(x - 1), i == n - 1 ? '\n' : ' '); update(x, 1); } return 0; }

逻辑说明：query(x - 1)查询的是值域中小于x的元素个数，这里必须减 1，因为题目要求“比自己小”，等于自己的不算。update(x, 1)表示当前值x出现了一次，要把它放进树状数组。每次查询和更新的值域下标都是x本身，而不是数组中的位置下标，这是这道题和普通前缀和题最大的不同。

参数说明：MAXV要开到值域上限而非n。如果读入的数据最大值是 1000000，树状数组长度就要能覆盖到 1000000，否则update循环会越界访问。这也是我反复强调数组按值域开的一个原因。输出格式里用%c控制空格和换行，是为了避免行尾多一个空格被判题机判错。

4.3 提交时容易被卡住的细节

本地跑这份.c文件没问题，但提交到 OJ 时有三个习惯能少踩坑。第一，如果用的是 Windows 环境，提交时要把源码重新用记事本或 IDE 另存为 UTF-8 或 ASCII 编码，中文注释偶尔会引发编译乱码问题，我一般直接删掉中英文注释再交。第二，C 语言的代码选 C 语言提交，别套 C++ 编译器，这个题用scanf和printf已经足够快，不需要cin的优化技巧。第三，MAXV不要为了省空间开得刚好等于最大值边界，留出 5 到 10 的余量，防止极端数据越界。

5. 避坑实录：树状数组最容易翻车的四个细节

5.1 下标从 0 开始导致 update 死循环

现象：程序运行后没有任何输出，CPU 占用 100%，或者本地执行直接卡死，但在小数据上偶尔又是对的。

原因：lowbit(0) = 0。下标为 0 时，update循环里i += lowbit(i)永远加 0，跳不出循环。输入数据里出现 0 时，如果直接当作下标插入，就会触发这个问题。

解决：所有进入树状数组的下标统一加 1 做偏移。读入x后，用update(x + 1, 1)插入，用query(x)查询比它小的个数。这道题里如果允许值等于 0，偏移是必须的，不要依赖题目说数据为正数就跳过。

5.2 数组大小按 n 开而不是按值域开

现象：小数据 AC，提交后偶尔运行时错误（Runtime Error），或者本地调试时数组越界但没报错。

原因：树状数组的下标是数字本身，而不是序列位置。题目说n <= 100000，但值域可能是1000000000，把tree开到n + 5根本覆盖不了这么大的下标。

解决：先看值域范围，如果值域太大，就要对输入数据做离散化，把原始值映射到1到n的连续整数。离散化的具体写法放到后面说，这里只记住一个原则：树状数组的下标范围，跟原数组长度无关，只跟你要维护的值的范围有关。

5.3 区间和错误地用两侧节点相加实现

现象：读到了这类题的错误写法后，查询[l, r]时从l和r同时向上走，把路径上的节点值全部相加，结果比正确答案大很多。

原因：树状数组的每个tree[i]只负责一个后缀型区间，从左侧向上走时，访问到的节点其实跨越了很多不相关的区间。上述做法把本来应该拆开求差的部分重复累加进去了。

解决：区间和永远用query(r) - query(l - 1)。先确认query返回的是从 1 到传入下标的闭区间前缀和，再做减法，不要自己发明“双向逼近”的算法。

5.4 lowbit 表达式优先级踩坑

现象：模板拷过来后，lowbit写成了return x & -x;，部分编译器警告，运算结果不稳定；或者写成了return x - (x & (x - 1));的变体但类型不匹配。

原因：&的优先级低于-，某些情况下x & -x会被解析成x & (-x)，多数编译器没问题，但可读性差，而且老编译器可能给出警告。另一个函数x & (x - 1)在二进制里是去掉最低位 1，和 lowbit 的语义并不完全相同，混用会导致跳跃路径错误。

解决：统一写成x & (-x)，或者给替换写法加括号。拿到任何模板，第一件事就是把lowbit单独拎出来测三个值：lowbit(1) = 1、lowbit(4) = 4、lowbit(6) = 2，对不上就直接改。

6. 进阶：离散化和逆序对，让这套模板覆盖更大值域

如果你已经能在《小鱼比可爱》这类题里用模板 AC，下一步值得练两个变体：离散化处理大值域，以及逆序对统计。

当值域达到10^9级别时，想直接开tree[1e9]是不现实的。常见做法是把所有输入值收集起来，排序去重，然后把每个原始值映射成它在有序数组中的排名，排名范围就到n以内了：

vector<int> a, b; sort(b.begin(), b.end()); b.erase(unique(b.begin(), b.end()), b.end()); for (int i = 0; i < a.size(); i++) { int idx = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1; // 对 idx 做 update 和 query }

逻辑说明：b是排序去重后的有序数组，lower_bound找到原始值在b中的位置，加 1 是为了让排名从 1 开始，避免 0 下标。离散化之后，树状数组的长度只需要n + 5，但查询语义完全不变。

逆序对是同一套模板的天然应用。思路是从右往左扫：每次遇到一个数，先查询已经扫过的数中有多少比它小，这些比它小的数在原始顺序里就构成了和当前数的逆序对，然后再把当前数插入。核心操作只有两行：

ans += query(idx - 1); update(idx, 1);

query(idx - 1)统计的是已扫描元素中排名小于当前数的个数，update(idx, 1)把当前排名插入值域树。整个过程下来，ans就是逆序对总数，复杂度O(n log n)。

我自己的教训是：有一段时间拿到模板就复制，结果在某个大值域题里忘做离散化，本地小数据全对，提交后每次都在第 18 个测试点崩掉，最后才发现tree数组越界了大半屏。从那以后，我每次用树状数组模板都强制自己走一遍“先测 lowbit 三个值、再确认值域范围和离散化、最后写 query(r)-query(l-1)”的流程，再也没在基础问题上翻过车。这套流程也建议你直接固化下来，希望帮到你。

本文还有配套的精品资源，点击获取