先讲一个真实场景。你在CSP-S复赛的考场上拿到一道数据范围 1e5 的数组题目，要求单点修改、区间求和。如果只会前缀和加暴力，改一次就是 O(n)，十万次操作直接奔着 1e10 复杂度去，差不多能跑到你交卷；而旁边的人只写了一个 30 行的树状数组，单次修改和查询都是 O(log n)，一道题轻松跑进 1 秒。差距往往就来自这个“不起眼”的数据结构。
树状数组，英文是 Fenwick Tree，在信奥赛提高组 C++ 的考纲里属于重点数据结构之一。它代码短、常数小，还能套上离散化、二分、差分、二维扩展去处理各种区间问题，CSP-S 初赛会考原理，复赛则是代码题的常客。这篇博文我把它拆成心智模型、模板代码、真题组合考法、避坑清单四个部分写出来，希望能让你从“背代码”变成“随手写”。
1. 为什么CSP-S提高组考点里，树状数组绕不开
1.1 树状数组在信奥赛里的定位
很多刚进提高组训练的同学会先学线段树，然后觉得树状数组就是个“阉割版”，没必要单独研究。实际情况恰恰相反，在 CSP-S 的赛场上，树状数组的出场频率一点都不低，甚至比线段树更能体现选手对复杂度的直觉。
原因其实很现实：树状数组的代码量太少。一个核心类封装下来，单点修改加区间查询不超过 15 行，考试时写起来快，调起来也快。而线段树稍不注意就会在 update 和 query 里漏掉 pushdown，调到心态崩溃。再加上树状数组底层只是若干个 int/long long 数组，常数远小于递归实现的线段树，在 1e5、1e6 级别的数据量下优势非常明显。
信奥赛初赛第一轮经常直接在选择题里问你“树状数组单点修改的时间复杂度”“lowbit(x) 的值”这类细节。而复赛大题的经典套路更加直接：后缀排名、逆序对、离线区间去重、动态第 k 小，全都绕不开树状数组。可以说，没掌握树状数组的人，遇到这些题就只能瞪着线段树，或者干脆暴力骗部分分。
1.2 学树状数组前，建议先掌握这些
我不建议你零基础直接硬啃树状数组，前置知识虽然不多，但缺一个都可能让你“代码是抄懂了，一到换题就懵”。
第一是位运算基础。树状数组的核心 lowbit 操作就是x & -x，如果你不清楚二进制补码、负数的表示方式，后面所有代码都像是在背天书。第二是前缀和思想。树状数组本质上解决的是“动态前缀和”，你得习惯把“区间 [l, r] 的和”理解成sum(r) - sum(l-1)。第三是循环和函数封装，C++ 基础语法要过关，CSP-S 复赛不是让你写 hello world，代码组织混乱会直接拖垮调试速度。第四是二分查找，树状数组上二分求第 k 小值时需要用到。
如果你这些都会，那本文对你来说就刚刚好；如果还想再稳一点，我的建议是先把前缀和和二分练熟，再来读后面的模板和真题拆解。
2. lowbit 是灵魂：一次性把原理讲透
2.1 用“连续段”理解二叉索引树
很多人看到树状数组的树形结构图会头晕，因为它并不是常见的二叉树，而是一种“二进制索引树”。我每次给新选手讲的时候，都建议他们先别管树，先把视角落到区间分段上。
假设你有一个长度为 8 的数组，下标从 1 到 8。树状数组的每个节点tree[i]并不是简单地存a[i]，它负责的是一个区间：从i - lowbit(i) + 1到i的所有元素之和。举个例子，tree[8]的 lowbit 是 8，所以它存的是a[1] + ... + a[8]；tree[6]的 lowbit 是 2，它只存a[5] + a[6]。
这样做有个非常大的好处：任何一个前缀和，都可以拆成若干个“长度正好是 2 的幂”的连续段。比如查询前 7 个元素的和，7 的二进制是 0111，于是可以拆成tree[7]（长度1）、tree[6]（长度2）、tree[4]（长度4）三段。把这三段加起来，就得到了a[1]到a[7]的总和。这个拆分次数最多是二进制位数，也就是 O(log n)，所以查询才快。
2.2 lowbit 的计算与两处关键行为
lowbit 的定义是“一个数二进制表示中，最低位的 1 和它后面所有 0 组成的数”。比如 6 的二进制是 0110，lowbit(6) 就是 0010，也就是 2；8 的二进制是 1000，lowbit(8) 是 8 本身，因为最低位 1 在第 4 位。
C++ 里一行代码算出来：x & -x。原理要稍微想一下：负数在补码表示下，等于原数按位取反再加 1。x & -x的结果，恰好就只保留最低位的那个 1。我见过很多选手在这里直接背，但其实只要拿笔算一遍 6 和 -6 的补码，这个操作就再也忘不掉了。
有了 lowbit，树状数组就有两个极其关键的移动方向：
- 单点修改时，从下标
i开始，每次i += lowbit(i)，更新所有包含a[i]的区间节点； - 前缀和查询时，从下标
i开始，每次i -= lowbit(i)，把对应的区间节点累加进结果。
“加”是往上找祖先，“减”是往左拆区间。这两个方向只要记反一个，程序立刻错得离谱。我的记忆方法是：修改要让“上层的兄弟也知道”，所以向上；查询是“把左侧的碎片捡起来”，所以向左。
2.3 单点修改、前缀和查询为什么会 log n
每个操作循环多少次？这完全取决于二进制里去除 lowbit 或累加 lowbit 的过程。
比如修改a[3]，二进制是 11，之后跳转到 100（4），再跳到 1000（8），再跳到 10000（16），一路翻倍向上。查询前缀和时，比如查前 7 个，是 111 → 110 → 100 → 0，相当于每次把最低位的 1 消掉。不管是往上进位还是往下消位，最多都不会超过二进制位数，也就是 log2(n) 级别的次数。
所以整体复杂度是 O(log n)。这里面的常数还非常小，因为循环体里只有一次数组访问和一次加法，比线段树的 if-else 分支和递归栈调用快得多。这就是为什么在同样的复杂度下，树状数组在跑大样例时经常“稳得一匹”。
3. 六个核心模板：抄完注释就能用
3.1 一维最基础版：单点修改 + 区间求和
这一版是所有树状数组代码的地基，考试时我会直接封装成结构体，省得每次写一堆裸函数。代码如下：
using ll = long long; struct Fenwick { int n; vector<ll> tree; Fenwick(int n) : n(n), tree(n + 1, 0) {} void add(int pos, ll val) { for (int i = pos; i <= n; i += i & -i) { tree[i] += val; } } ll sum(int pos) { ll res = 0; for (int i = pos; i > 0; i -= i & -i) { res += tree[i]; } return res; } ll rangeSum(int l, int r) { return sum(r) - sum(l - 1); } };注意几个细节。下标位置必须从 1 开始，所以调用时如果原数组是 0 下标，要传入pos + 1。构造函数里tree长度为n + 1，访问下标 1..n。add的循环条件是i <= n，这样当pos = n时，i只会跳到 n 就停，不会越界。sum则相反，i不断减，注意循环以i > 0结束。
使用场景很直接：维护一个初始数组，支持把某个位置加上一个数，然后询问某段区间的和。如果题目要求“把某个位置改成 x”，只需要调用add(pos, x - old[pos])，相当于先把旧值抵消再加新值。
3.2 差分改造：区间修改 + 单点查询
如果题目只要求“区间都加一个值，再查询某个单点是多少”，普通的树状数组就用不了了。这时候要引入差分数组。
设原数组是a[1..n]，差分数组d[i] = a[i] - a[i-1]。对区间[l, r]做全体加val这件事，反映到差分数组上，其实只需要两个位置的改变：d[l] += val，d[r+1] -= val。这样一来，“区间修改”被转化成了“单点修改”，而“单点查询a[x]”等于求d[1] + d[2] + ... + d[x]，即前缀和。
于是可以直接复用上面的树状数组，只不过存的对象从a变成了d：
Fenwick fw(n); void rangeAdd(int l, int r, ll val) { fw.add(l, val); if (r + 1 <= n) fw.add(r + 1, -val); // 注意右边界 } ll pointQuery(int x) { return fw.sum(x); }这里有个很容易踩的坑：如果r + 1 > n，再调用fw.add(n + 1, -val)是多余且无意义的，虽然循环条件i <= n会拦住更新不越界，但逻辑上建议直接跳过，也更符合差分数组的定义。
3.3 进阶双树版：区间修改 + 区间求和
有些题更离谱，既要区间加，又要区间求和。这时候需要在差分基础上维护两个树状数组，推导可以一步步来。
我们用差分数组d[i]表示变化量，那么a[x] = d[1] + d[2] + ... + d[x]，而区间[1, x]的和可以写成：
sum_{i=1}^x a[i] = sum_{i=1}^x sum_{j=1}^i d[j] = sum_{j=1}^x d[j] * (x - j + 1) = (x + 1) * sum_{j=1}^x d[j] - sum_{j=1}^x j * d[j]所以只要同时维护两个树状数组，一个存d[j]，一个存j * d[j]，就能在 O(log n) 内完成所有操作。代码实现如下：
class BitRange { private: int n; vector<ll> b1, b2; void add(vector<ll>& bit, int idx, ll val) { for (int i = idx; i <= n; i += i & -i) bit[i] += val; } ll sum(vector<ll>& bit, int idx) { ll res = 0; for (int i = idx; i > 0; i -= i & -i) res += bit[i]; return res; } public: BitRange(int n) : n(n), b1(n + 1), b2(n + 1) {} void rangeAdd(int l, int r, ll val) { add(b1, l, val); add(b1, r + 1, -val); add(b2, l, val * l); add(b2, r + 1, -val * (r + 1)); } ll prefixSum(int x) { if (x <= 0) return 0; return sum(b1, x) * (x + 1) - sum(b2, x); } ll rangeSum(int l, int r) { return prefixSum(r) - prefixSum(l - 1); } };这种写法在竞赛里很实用。考试时如果你没背过模板，建议把前面的公式在草稿纸上推导一遍再写，能大幅降低出错概率。至少我自己是这么干的，一遍推熟以后，双树法基本不会再写错。
3.4 二维扩展：单点修改 + 子矩阵求和
有时候题目会把数组变成二维矩阵，支持修改某个点，查询某个矩形区域的元素和。树状数组照样能扩展，只是把两重循环叠起来。
struct Fenwick2D { int n, m; vector<vector<ll>> tree; Fenwick2D(int n, int m) : n(n), m(m), tree(n + 1, vector<ll>(m + 1, 0)) {} void add(int x, int y, ll val) { for (int i = x; i <= n; i += i & -i) { for (int j = y; j <= m; j += j & -j) { tree[i][j] += val; } } } ll sum(int x, int y) { ll res = 0; for (int i = x; i > 0; i -= i & -i) { for (int j = y; j > 0; j -= j & -j) { res += tree[i][j]; } } return res; } ll rectSum(int x1, int y1, int x2, int y2) { return sum(x2, y2) - sum(x1 - 1, y2) - sum(x2, y1 - 1) + sum(x1 - 1, y1 - 1); } };二维树状数组的复杂度变成 O(log n * log m)，虽然看起来慢了一点，但对 1000x1000 左右的矩阵还是能扛住的。记住矩形求和的容斥公式：左上右下的大矩形，减去左下边界，减去右上边界，再加上多减掉的左上角。
3.5 离散化 + 树状数组：逆序对模板
逆序对是 CSP-S 的高频题，也是最经典的一道“树状数组 + 离散化”例题。先解释思路：如果数组值域很大，比如1e9，就没法直接按下标建树状数组。做法是先把所有数字排序，用排名代替原数值，压缩成1..n的整数。
然后从左到右扫描原数组。每看到一个数字，就在树状数组中“在它的排名位置加 1”，表示这个值已经出现了一次。此时树状数组的sum(idx - 1)就能告诉我在当前数字之前、比它小的数字有多少个。而当前已经扫过的数字总共有i个，减去比它小的数量，得到的就是“之前比它大的数量”，也就是以当前位置构成的逆序对个数。
vector<int> a; vector<int> sorted = a; sort(sorted.begin(), sorted.end()); auto getId = [&](int x) { return int(lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin()) + 1; }; Fenwick fw(n); long long ans = 0; for (int i = 0; i < n; i++) { int id = getId(a[i]); ans += i - fw.sum(id - 1); fw.add(id, 1); }这里的getId用lower_bound把每个值映射到它的排名，映射后相同值会映射到同一个 id，这样就实现了去重。逆序对的答案要用long long存，在n = 1e5时逆序对数量最高接近5e9，int必炸。
3.6 树状数组上二分：求第 k 小
树状数组不仅支持求和，还能配合二分用于“动态求第 k 小”。经典场景是：不断插入一些数，然后询问当前所有数中第 k 小的数是多少。如果用普通multiset也能写，但树状数组的写法效率和常数都更优。
原理其实不复杂。树状数组的tree[i]节点天然覆盖一段长为 lowbit 的区间，我们从最高的 2 的幂开始向下试探，看累加之后有没有超过 k。如果没超过，就前进到这个位置，继续往下试；如果超过，就说明答案在当前位置之后的更小范围内。这就是所谓的“倍增法”。
int kth(long long k) { int idx = 0; // 找到不超过 n 的最大 2 的幂 int step = 1; while (step * 2 <= n) step <<= 1; for (; step; step >>= 1) { int nxt = idx + step; if (nxt <= n && tree[nxt] < k) { k -= tree[nxt]; idx = nxt; } } return idx + 1; }这里有个易错点：tree[nxt]的含义是区间和，不是“nxt 位置的值”，所以在跳跃时要用tree[nxt] < k这个判断。循环结束时idx是满足“前缀和小于 k”的最大位置，那么答案就是idx + 1。
4. 初始化树状数组：暴力 update 和线性建树的取舍
4.1 常见初始化方法：直接 update
最直观的建树方式是先让树状数组全为 0，然后遍历原数组每个位置，调用add(i, a[i])。这个复杂度是 O(n log n)，在绝大多数题目里完全够用。
Fenwick fw(n); for (int i = 1; i <= n; i++) { fw.add(i, a[i]); }这是我考试时最常用的方法，因为它足够简单，不会因为手写复杂建树而出错。尤其是很多题目的初始数组还可能只用来“铺垫”，后面全是动态操作，O(n log n) 建树的那点时间几乎可以忽略不计。
4.2 线性建树的原理与代码
如果你想追求极致效率，或者一次性要建立好多个树状数组，可以用线性建树法。思路是利用树状数组的父子关系，i的父节点是i + lowbit(i)，所以可以先让tree[i]暂时存原数组a[i]的值，再从1..n按顺序把自己的值累加给父节点。
void build(int a[], int n) { for (int i = 1; i <= n; i++) { tree[i] += a[i]; int j = i + (i & -i); if (j <= n) { tree[j] += tree[i]; } } }为什么是对的？因为tree[i]一开始只存了原数组中单独的值a[i]，但正因为它表示的是连续一段的和，所以它需要把这一段所有元素都汇总。当从 1 到 n 扫描时，每个tree[i]在进入父节点前已经把前序相关的值都加进来了，这样父节点最终拿到的是完整的区间和。这个结论可以自己拿n = 8手算一遍，比纸上画图体会更深。
4.3 赛场到底用哪一套
我的个人建议很直接：如果不是题目特意卡初始化时间，直接for循环update建树就行。线性建树虽然省了一个 log，但代码不直观，一旦tree里还有历史值没有清空，很容易出隐蔽的错误。CSP-S 考场上最重要的是稳定，复杂度多一个 log 只要能过，就完全不是问题。
真要追求那点常数，也要在本地用大样例验证过再换。我见过不少选手为了省时间用线性建树，结果漏了初始化，最后花二十分钟查 bug，反而得不偿失。
5. CSP-S 真题视角：树状数组怎么和别的算法组合
5.1 动态中位数 / 动态第 k 小
求静态中位数很简单，排个序取中间就行；但“动态中位数”要求每插入一个数就输出当前序列的中位数，这就很自然地用到了树状数组上的二分。
思路是：把所有可能出现的值离散化，然后逐个插入。每次插入把对应位置的计数加 1，然后用kth((cnt + 1) / 2)求出当前第“中间”大的数。整个过程 O(n log n)，代码核心就是第 3.6 节的kth函数。这个套路在数据流处理、在线排名类问题里经常跟“堆”的方案做对比。虽然对顶堆也能写，但树状数组版本不需要维护两个堆，思维负担更小。
5.2 离线区间去重计数
有一类题长这样：给你一个静态数组，多次询问某个区间内有多少个不同的数字。这种题初次见面很难想到树状数组，但它是经典离线套路。
做法是把所有询问按右端点排序。然后从左到右扫描原数组，用一个数组last[x]记录数值x上一次出现的位置。扫到位置pos时，如果last[a[pos]]已经存在，就在树状数组的last[a[pos]]位置减 1；然后在当前pos位置加 1，并更新last[a[pos]] = pos。这样每扫到一个位置，树状数组里“值为 1 的位置”就是每个数字在当前扫描前缀中最后出现的位置。
对于所有右端点等于pos的询问，答案就是sum(r) - sum(l - 1)，也就是区间[l, pos]里最后出现位置的个数。这个思路很值得反复琢磨，因为它在“离线处理”里特别经典，和“CDQ 分治”“扫描线”是一脉相承的思想。
5.3 二维偏序与动态规划优化
树状数组还能用来优化动态规划。比如最长上升子序列（LIS）的计数类问题，常规 DP 是 O(n^2)，但如果把每个值离散化，就能用树状数组维护“以某个值结尾的最长上升子序列长度和方案数”。
假设你要求以当前元素结尾的 LIS 长度，就需要查询在它之前、且值小于它的元素中，最长的 dp 值是多少。这刚好对应树状数组的“前缀最大值”查询：把dp[val]存进树状数组，查询sum(val - 1)时取的不是累加和，而是区间最大值。再配合一个计数数组维护方案数，就能把这类 DP 优化到 O(n log n)。
这种“树状数组 + DP”的组合在提高组第三题里经常出现，虽然不一定直接叫树状数组题，但你在推导完转移方程后会发现，优化部分无非就是在数据结构上做文章。能把树状数组当成一个顺手可用的优化工具，比单纯会写模板更有区分度。
6. 避坑清单：这些都是赛场真实翻车点
6.1 下标从 1 开始还是从 0 开始
这是树状数组新手犯的第一个错误。i += lowbit(i)和i -= lowbit(i)对i = 0都是死循环，所以树状数组必须以下标 1 为逻辑起点。
写封装时最好约定：外部接收的pos是 1-indexed。如果题目给的是 0-indexed 数组，传入时手动加 1。千万不要在add函数里面偷偷减一，那样不同调用点很容易混乱。我的习惯是封装内部统一 1-indexed，外部接口做好提示，自己写题时也能少踩坑。
6.2 数据范围与 long long，别赌 int
树状数组是个“累加器”，累加过程中特别容易溢出。假设n = 1e5，每个数最大1e9，单次前缀和就可能到1e14，稳稳超过int范围。所以涉及求和的res、tree数组建议直接开long long。
需要申明的是，有些题目确实用int能过，但这种好运气在 CSP-S 真题里不值得赌。开long long不会让代码变慢多少，却能帮你在考场上少挂一个数据点。范围修改题里val * l这种中间结果，也记得确保val已经是long long，避免先按int相乘再隐式转换。
6.3 树状数组和线段树的选择边界
有些同学看到区间最大值、区间覆盖修改这类题，会硬套树状数组。树状数组不适合做需要“区间整体覆盖”“区间懒标记”的操作，比如把一个区间内所有数都赋成同样的值，然后查区间和，这时候线段树的 lazy tag 就比树状数组自然得多。
我的选择逻辑很简单：如果是“单点修改 + 区间查询”“逆序对”“计数类前缀”这几类，优先树状数组；如果涉及“区间整体赋值、区间乘、区间最值、需要维护多个标记”，直接上线段树。树状数组代码短、好调，但设计空间有限，不要指望它包打天下。能把两个数据结构在合适的时间用对，才是真正的赛场竞争力。
