之前在算法训练中反复使用树状数组解决区间求和、动态排名等问题发现网上资料虽然多但往往只讲模板不讲为什么这样写。遇到区间修改、逆序对、树上二分这些进阶场景时零零散散翻了不少文章才拼出完整思路。这篇文章把树状数组从原理到高阶应用做一次系统梳理包含完整的代码模板、复杂度分析和踩坑记录竞赛选手和准备面试的开发者都可以直接参考。1. 树状数组是什么1.1 树状数组解决什么问题树状数组Binary Indexed TreeBIT是一种用于维护数列前缀和、支持单点修改和区间查询的数据结构。它由 Peter M. Fenwick 在 1994 年提出因此也叫 Fenwick Tree。先看一个经典场景维护一个长度为n的数组需要支持两类操作修改某个位置的值例如a[i] x。查询区间[l, r]的和。如果只用普通数组修改是O(1)查询需要遍历区间最坏是O(n)。如果预处理前缀和数组那么查询是O(1)但修改需要更新后面所有位置的前缀和最坏是O(n)。当n很大、操作次数很多时这两种做法都不够高效。树状数组用二进制思想把两种操作都优化到O(log n)实现代码又非常短只有十几行因此成为算法竞赛和工程开发中非常常用的数据结构。1.2 树状数组和线段树的区别很多初学者会问有了线段树为什么还要学树状数组两者确实都能处理区间查询和单点修改但有明显差异对比维度树状数组线段树代码长度很短约 15 行较长约 80-120 行常数小运行快较大递归建树/查询有额外开销支持区间修改需要差分技巧需要懒标记lazy tag查询区间最大值/最小值不擅长需额外处理天然支持可扩展性适合前缀类信息适合多种区间聚合信息一句话总结树状数组能解决的问题是线段树的子集但树状数组实现简单、常数小能用树状数组时优先用树状数组。遇到需要维护区间最值、区间最大子段和等复杂信息时再上线段树。2. 环境准备与版本说明树状数组是纯算法逻辑不依赖特定编程语言版本或操作系统。只要支持数组和基础位运算就能实现。下面以最常见的学习环境为例编程语言C竞赛最常用、Java、Python 均可编译环境C11 及以上或者任意 Python 3.x开发工具Visual Studio Code、CLion、Dev-C、或直接在在线判题系统上编写本文的示例以 C 为主同时也给出 Python 版本作为参考。算法本身在任何语言下思路完全一致只是语法不同。如果本地需要验证建议建一个简单的控制台项目即可不需要额外安装库。核心代码只有一个数组和两个函数。3. 树状数组的核心原理3.1 lowbit 运算树状数组的第一个关键概念是lowbit。lowbit(x)表示正整数x的二进制表达式中最低位的1所对应的数值。例如x 6二进制为110最低位的1对应10即2所以lowbit(6) 2。x 8二进制为1000最低位的1对应1000即8所以lowbit(8) 8。x 5二进制为101最低位的1对应1所以lowbit(5) 1。计算lowbit的公式很简单int lowbit(int x) { return x (-x); }为什么x (-x)能得到最低位的1因为在补码表示中-x等于~x 1。~x把所有位取反加 1 后x最低位的1所在位置及其右边保持不变更高位全部取反。这样x (-x)的二进制结果恰好只保留了最低位的1。这个运算虽然只有一行但它是树状数组所有操作的基石。3.2 树状结构的设计思想树状数组维护的并不是原数组本身而是一个基于二进制分解的累加结构。设原数组为a[1..n]树状数组为t[]。树状数组的第i个位置t[i]存储的是原数组中某一特定区间的和。具体规则t[i] sum(a[i - lowbit(i) 1 .. i])也就是说t[i]管理的是从i - lowbit(i) 1到i这个长度为lowbit(i)的区间和。举个例子假设n 8那么t[1] a[1]因为lowbit(1) 1t[2] a[1] a[2]因为lowbit(2) 2t[3] a[3]因为lowbit(3) 1t[4] a[1] a[2] a[3] a[4]因为lowbit(4) 4t[5] a[5]t[6] a[5] a[6]t[7] a[7]t[8] a[1] ... a[8]可以看到下标为奇数的位置只存原数组对应位置的值下标为 2 的幂次的位置存的是一个前缀和。这种设计有一个重要性质从任意位置i往前求和时只需要不断减去lowbit(i)就能覆盖到所有需要累加的区间且不重不漏。3.3 为什么复杂度是 O(log n)树状数组的修改操作中下标更新方式是i lowbit(i)查询操作中下标更新方式是i - lowbit(i)。这两种操作的本质都是二进制位的变化。每次加或减lowbit都会把二进制中最低位的1消除或进位。由于一个整数最多有O(log n)个二进制位所以操作次数不会超过O(log n)。这也是树状数组高效的根本原因它利用二进制的结构把区间信息切分成若干个长度恰好是2的幂的子区间任何前缀都能用这些子区间拼出来。4. 树状数组的基本操作详解4.1 单点修改操作单点修改的目的是让原数组某个位置的值变化同时更新所有包含该位置的树状数组节点。比如原数组a[i]增加了x那么所有管理范围覆盖i的t[j]都要加上x。这些j的规律是j i; while (j n) { t[j] x; j lowbit(j); }从i开始不断加上自身的lowbit就能依次找到所有父节点。举个例子如果修改a[3]那么需要更新t[3]、t[4]、t[8]因为lowbit(3) 13 1 4lowbit(4) 44 4 8这三个位置的管理范围确实都包含下标3。4.2 前缀和查询查询1到pos的和时从pos开始不断累加t[pos]然后pos - lowbit(pos)。int query(int pos) { int sum 0; while (pos 0) { sum t[pos]; pos - lowbit(pos); } return sum; }比如查询1到6的和pos 6累加t[6]它管理a[5] a[6]pos 6 - lowbit(6) 4累加t[4]它管理a[1] a[2] a[3] a[4]pos 4 - lowbit(4) 0停止所以query(6) t[6] t[4]正好等于a[1]到a[6]的总和。4.3 区间和查询有了前缀和区间[l, r]的和可以转换为两个前缀和相减int rangeQuery(int l, int r) { return query(r) - query(l - 1); }这里要注意下标从 1 开始因为lowbit(0)没有意义树状数组的循环依赖下标为正数。如果原数组从 0 开始需要把所有下标整体加 1。5. 完整实战单点修改 区间查询5.1 问题描述给定一个长度为n的数组初始值为a[1..n]。接下来有m次操作分成两类1 i x把a[i]增加x2 l r查询区间[l, r]的和其中1 n, m 100000。这是树状数组最基础的模板题适合作为第一个完整练习。5.2 C 完整实现文件路径main.cpp#include bits/stdc.h using namespace std; const int MAXN 100005; int n, m; long long t[MAXN]; int lowbit(int x) { return x (-x); } void add(int i, int x) { while (i n) { t[i] x; i lowbit(i); } } long long query(int pos) { long long res 0; while (pos 0) { res t[pos]; pos - lowbit(pos); } return res; } long long rangeQuery(int l, int r) { return query(r) - query(l - 1); } int main() { ios::sync_with_stdio(false); cin.tie(0); cin n m; for (int i 1; i n; i) { int x; cin x; add(i, x); } while (m--) { int op, a, b; cin op a b; if (op 1) { add(a, b); } else { cout rangeQuery(a, b) \n; } } return 0; }这里把t[]定义为long long是因为区间和可能超过int范围尤其是多次累加之后。用long long可以避免不必要的溢出问题。5.3 Python 完整实现def lowbit(x: int) - int: return x (-x) class FenwickTree: def __init__(self, n: int): self.n n self.t [0] * (n 1) def add(self, i: int, x: int) - None: while i self.n: self.t[i] x i lowbit(i) def query(self, pos: int) - int: res 0 while pos 0: res self.t[pos] pos - lowbit(pos) return res def range_query(self, l: int, r: int) - int: return self.query(r) - self.query(l - 1) n, m map(int, input().split()) a list(map(int, input().split())) bit FenwickTree(n) for idx, val in enumerate(a, start1): bit.add(idx, val) for _ in range(m): op, x, y map(int, input().split()) if op 1: bit.add(x, y) else: print(bit.range_query(x, y))5.4 运行验证输入5 4 1 2 3 4 5 2 1 3 1 2 3 2 1 5 2 2 5第一行表示数组长度n5操作次数m4。初始数组为[1, 2, 3, 4, 5]。查询[1, 3]和为1 2 3 6将a[2]增加3数组变为[1, 5, 3, 4, 5]查询[1, 5]和为18查询[2, 5]和为5 3 4 5 17预期输出6 18 176. 进阶实战区间修改 区间查询6.1 差分思想上一节处理的是“单点修改 区间查询”。如果题目要求“区间修改 单点查询”通常用差分数组配合树状数组解决。设原数组为a[1..n]定义差分数组d[i] a[i] - a[i-1]a[0] 0。那么对a[l..r]区间整体加x等价于d[l] x d[r 1] - x这样区间修改就变成了差分数列上的两次单点修改。查询某个位置a[i]的值等价于求差分数组d的前缀和d[1] d[2] ... d[i]。如果要在区间修改的同时支持区间查询就需要再多维护一个树状数组。6.2 维护两个树状数组推导区间查询的本质是求前缀和S(x) a[1] a[2] ... a[x]。用差分表示S(x) sum_{i1..x} a[i] sum_{i1..x} sum_{j1..i} d[j]交换求和顺序发现S(x) (x 1) * sum_{i1..x} d[i] - sum_{i1..x} i * d[i]因此只要同时维护两个树状数组b1维护差分数组d[i]b2维护i * d[i]的累加结果就能在O(log n)内完成区间修改和区间查询。6.3 完整代码实现#include bits/stdc.h using namespace std; const int MAXN 100005; int n, m; long long b1[MAXN], b2[MAXN]; int lowbit(int x) { return x (-x); } void update(long long bit[], int i, long long x) { while (i n) { bit[i] x; i lowbit(i); } } long long query(long long bit[], int i) { long long res 0; while (i 0) { res bit[i]; i - lowbit(i); } return res; } // 区间 [l, r] 整体增加 x void rangeAdd(int l, int r, long long x) { update(b1, l, x); update(b1, r 1, -x); update(b2, l, x * (l - 1)); update(b2, r 1, -x * r); } // 前缀和 S(x) long long prefixSum(int x) { return query(b1, x) * x - query(b2, x); } // 区间和 [l, r] long long rangeSum(int l, int r) { return prefixSum(r) - prefixSum(l - 1); } int main() { ios::sync_with_stdio(false); cin.tie(0); cin n m; long long last 0; for (int i 1; i n; i) { long long cur; cin cur; long long d cur - last; update(b1, i, d); update(b2, i, d * (i - 1)); last cur; } while (m--) { int op; cin op; if (op 1) { int l, r; long long x; cin l r x; rangeAdd(l, r, x); } else { int l, r; cin l r; cout rangeSum(l, r) \n; } } return 0; }6.4 推导细节说明区间修改部分从差分数组的定义出发d[l] x d[r 1] - x对于b2维护的是i * d[i]l 位置增加 x * l r 1 位置增加 (-x) * (r 1)但在实际模板中很多写法会写成update(b2, l, x * (l - 1)); update(b2, r 1, -x * r);这里其实是把推导公式化简了因为prefixSum(x) x * sum(d[1..x]) - sum(i * d[i])中x是动态的无法把x放进差分更新里。用x * (l - 1)和-x * r是为了避免前缀和结果出现常数偏移。建议初学者直接记住这个更新方式在纸上手动推一次l2, r4的例子就能理解为什么这样更新。7. 树状数组的高阶应用7.1 求逆序对逆序对问题给定数组a[1..n]求有多少对(i, j)满足i j且a[i] a[j]。经典做法是归并排序但树状数组也能高效解决而且代码更直观。思路离散化把原数组映射为1..k的排名其中k n。从前往后扫描数组每遇到一个数x用树状数组统计当前已经出现过的数中大于x的个数。把x加入树状数组。换句话说遍历到a[i]时query(n) - query(a[i])就是与a[i]形成逆序对的元素个数。C 实现#include bits/stdc.h using namespace std; const int MAXN 500005; int n; long long t[MAXN]; struct Node { int val, idx; } a[MAXN]; int lowbit(int x) { return x (-x); } void add(int i, int x) { while (i n) { t[i] x; i lowbit(i); } } long long query(int i) { long long res 0; while (i 0) { res t[i]; i - lowbit(i); } return res; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin n; for (int i 1; i n; i) { cin a[i].val; a[i].idx i; } // 按值排序进行离散化 sort(a 1, a n 1, [](const Node u, const Node v) { return u.val v.val; }); vectorint rank(n 1); for (int i 1; i n; i) { rank[a[i].idx] i; } long long ans 0; for (int i 1; i n; i) { ans query(n) - query(rank[i]); add(rank[i], 1); } cout ans \n; return 0; }这里离散化的做法比较直接先按值排序再把原数组的每个位置替换为大小排名。如果原值中有重复元素排序时还需要仔细处理排名规则。实际竞赛题中常用另一种写法先排序再用lower_bound或unique去重再二分映射这样更简洁。7.2 树状数组上二分树状数组不仅可以求和还能在O(log n)时间内找到前缀和第一次达到某个阈值的位置。这个技巧被称为“树状数组上二分”常用于处理按权值计数的问题例如查找第k小元素。核心思路是利用树状数组下标二进制的结构从高位到低位枚举逐位确定答案。C 实现int findKth(int k) { int pos 0; // 2^LOG 是大于 n 的最大的 2 的幂 for (int i LOG; i 0; i--) { int nxt pos (1 i); if (nxt n t[nxt] k) { k - t[nxt]; pos nxt; } } return pos 1; }这个函数的含义是在树状数组的二进制结构上贪心移动跳过累加和小于k的块最终停留的位置就是第k个元素的位置。但需要注意这种二分要求树状数组内部维护的是非负的频次计数。如果维护的是前缀和且原数组有负数这个贪心策略不再保证正确因为t[]不一定单调递增。树状数组上二分的典型应用包括权值线段树的替代方案支持动态查询第k小在 O(log n) 时间内确定某个累计频次对应的下标解决“前缀和第一个超过k的位置”类问题7.3 离线查询与二维树状数组树状数组经常与离线处理结合。例如区间不同数字个数问题可以把所有查询按右端点排序边扫描边用树状数组维护每个数字最后一次出现的位置。每次遇到一个数字就在当前位置加 1如果之前出现过就把上次出现位置减 1。这样一个区间[l, r]的不同数字个数就是query(r) - query(l - 1)。二维树状数组则把一维数组扩展成二维矩阵。修改操作变为双层循环void add2D(int x, int y, int val) { for (int i x; i n; i lowbit(i)) { for (int j y; j m; j lowbit(j)) { bit[i][j] val; } } }二维树状数组适用于矩阵单点修改、子矩阵和的场景复杂度为O(log n * log m)。8. 常见问题与排查思路树状数组代码虽短但初学者容易踩坑。下面整理高频问题问题现象常见原因解决思路下标从 0 开始导致死循环lowbit(0)0i lowbit(i)永远为 0统一把下标改为从 1 开始查询结果偏小区间查询写成query(r) - query(l)正确写法是query(r) - query(l - 1)更新时数组越界while (i n)中n设置错误确认n是原数组长度同时树状数组大小至少为n 1数据溢出统计值超过int范围使用long long树状数组上二分结果错误数组中有负数或重复值处理不当确认维护的是非负频次重复值离散化时确定排名规则离散化后顺序错乱排序时没有同时保存原始下标用结构体保存值和下标再按值排序区间修改后单点查询错误忘记在r 1位置做减法检查 diff 更新的两个端点是否完整8.1 排查思路如果某个测试数据不通过建议按下面顺序排查检查下标是否从 1 开始尤其注意输入数组下标转换。手动模拟一个长度在 5 以内的小样例逐步打印t[]数组的变化。区分n的含义是数组长度还是最大下标是否在程序开头初始化。检查所有累加变量是否使用long long。如果有取模操作确认每一步取模的时机避免减出负数。如果是离散化打印映射后的rank数组确认每个原位置都映射到了正确排名。9. 工程建议与易错点9.1 通用代码规范lowbit函数建议写成inline减少函数调用开销。树状数组大小固定为n 1不要写成n否则最后一下更新可能越界。全局变量默认初始化为 0不需要重复 memset。如果使用局部数组记得初始化。多组输入时如果树状数组大小不同需要重新初始化通常用fill(t, t n 1, 0)而不是memset全部清空节约时间。9.2 性能优化建议关闭 C 的输入输出同步使用ios::sync_with_stdio(false)和cin.tie(0)或者直接用scanf/printf。在update和query频繁调用的场景下函数内避免额外判断和多余的递归。能用树状数组就不建议用线段树动态维护前缀和的场景树状数组常数更小。9.3 学习路径建议树状数组的进阶路线可以这样规划掌握lowbit和基本单点修改、区间查询模板。理解差分思想掌握区间修改 区间查询。练习逆序对和离散化。掌握树状数组上二分。扩展到二维树状数组、离线查询。学会把树状数组与数学推导、计数问题结合。每一步都可以在在线评测平台上找对应模板题练习边做题边总结比只读文章有效得多。10. 总结树状数组是算法竞赛中性价比最高的数据结构之一。它代码量少、运行速度快、思路清晰能解决一大类动态前缀和与区间统计问题。核心就是理解lowbit运算和二进制分解思想再把单点修改、前缀和查询两个基本操作练熟。本文从基本原理开始讲解了树状数组的存储结构、基本操作、区间修改的实现方式并给出了逆序对、树状数组上二分等高阶应用。如果你正在备赛或复习数据结构建议把每段代码都亲手敲一遍改一改参数观察输出变化。代码只有自己写一遍才能真正理解其中的二进制跳跃逻辑。如果这篇文章对你有帮助可以收藏备用方便刷题时快速查阅模板。也欢迎在评论区交流你在树状数组使用中遇到的奇怪问题一起讨论排错思路。