2026年1月12日我又把树状数组从头到尾完整推了一遍。树状数组是我在算法题里用得最频繁的基础数据结构之一凡是遇到单点修改、区间求和或者区间修改、单点查询我第一反应基本都是它。这篇文章是这次总结的记录也是我整理出的一份可以直接复用的树状数组模板和避坑清单。内容上我把原理、基础模板、扩展模型、经典题目、常见问题全串在一起适合准备竞赛的读者也适合工作中要处理动态前缀数据的程序员参考。1. 为什么我每年都要重新总结一遍树状数组1.1 先搞清楚树状数组到底解决什么问题树状数组解决的核心问题用一句话概括就是在一个可以动态修改的数组上快速维护前缀信息。最常见的例子是数组长度 n 达到 10^5操作次数 q 也是 10^5操作只有两种把某个位置的值加上一个数查询某个区间内所有元素的总和。如果暴力修改每次修改是 O(1)但每次区间查询都要从头加到尾最坏是 O(n)1e5 次操作跑出 1e10 量级的计算显然不可能。如果提前算好前缀和区间查询确实能做到 O(1)可一旦修改了某个位置的值它后面的所有前缀和都要跟着变单次修改又退化成 O(n)。这两个极端方案的问题在于修改和查询的代价没法同时压低。树状数组就是来解决这个矛盾的。它用 O(log n) 的代价完成单次修改也用 O(log n) 的代价完成前缀和查询空间只多开一个与原数组等长的一维数组。log n 在 n1e5 时大约是 17这意味着就算有 1e5 次操作总运算量也只有百万级别跑起来非常轻松。我最早接触它是在准备算法竞赛的时候后来发现它离实际工作也不远网站的访问量统计、订单金额的区间汇总、日志数据的计数查询只要数据在动态更新又需要汇总查询树状数组都有用武之地。1.2 和线段树相比树状数组赢在哪儿很多初学者会有个疑问既然已经有了线段树为什么还要学树状数组我的答案是线段树确实功能更全面但在特定场景下树状数组更值得选因为它更轻、更快、更容易写对。代码长度树状数组核心操作十行上下线段树建树、修改、查询动辄六七十行。常数性能树状数组没有递归栈开销循环次数少纯求和场景实测通常比线段树快 30% 到 50%。空间占用树状数组只需要一个 n1 的一维数组线段树保守要开 4n二维问题差距更明显。功能覆盖树状数组擅长处理可差分信息例如和、异或、计数线段树配合懒标记可以处理区间赋值、区间覆盖这类复杂操作。这不是说线段树没用。遇到需要区间取反、区间覆盖、维护最大连续子段和这类复杂合并信息时线段树依然是首选。但如果题目只要求改一个点、查一段区间用线段树就像拿电锯切西瓜费工费时还容易出 bug。模板题里这种差异最明显线段树也能过但树状数组敲完就能直接提交调试成本几乎为零。1.3 什么时候该用树状数组什么时候该绕道从我刷题和带新人的经验看树状数组真正发挥威力的场景集中在动态前缀和、区间求和、逆序对、二维偏序计数、差分维护区间修改。尤其是逆序对和二维偏序树状数组几乎是默认首选因为它天然维护了某个值域内已经出现了多少个元素的计数信息。反过来树状数组不太擅长区间最值查询、区间赋值、以及需要在下标段上做复杂合并的题目。虽然也有办法强行用树状数组维护最大值但代码会绕很多边界情况也多远不如线段树直接。学习门槛方面树状数组其实很低核心只要搞懂 lowbit 和 c 数组的管辖范围剩下基本就是套模板。我见过很多朋友被c[i] 到底存了什么这个问题卡住所以下面我用一整章专门把原理拆细。2. 树状数组的底层原理lowbit 才是真正的主角2.1 lowbit 怎么算为什么是这个式子树状数组的每个下标 i都管理一段长度为 lowbit(i) 的区间。lowbit 的定义是一个数在二进制下从最低位开始数第一个 1 及其后面所有 0 组成的数。比如 5 的二进制是 101lowbit(5) 等于 16 的二进制是 110lowbit(6) 等于 28 的二进制是 1000lowbit(8) 等于 8。计算方式一句话x -x。我第一次看到这行代码时也愣了很久为什么一个按位与就能拿到最低位的 1关键在于补码表示。一个负数在计算机里等于它的正数按位取反再加一所以x -x会把 x 左边的高位全部清零只留下最低位的那个 1。举 6 和 -6 的例子6 的二进制是 0110取反加一后 -6 的补码是 1010两者按位与得到 0010正好是 2。lowbit 是整个数据结构的枢纽修改和查询都靠它决定下标怎么跳。2.2 c[i] 到底在存什么管辖范围图树状数组的逻辑结构里代码维护的是辅助数组 c。很多人卡在 c[i] 是前缀和吗这个问题上其实不是。c[i] 存的是从 i-lowbit(i)1 到 i 这一整段区间的信息。为了看清这个规律把 n8 的情况列出来下标 ilowbit(i)c[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]你可以看到下标为奇数的节点只管自己下标为 2 的幂的节点管一段最长的前缀。整体结构像是一棵被压缩过的森林每个节点只管一段长度是 2 的幂的区间而这些区间在查询前缀和时可以无缝拼起来。理解了这张表后面所有循环代码都有了解释。2.3 单点修改管得宽的下标要先更新如果修改了原数组位置 pos 的值所有管辖范围包含 pos 的 c[i] 都要同步修改。这些下标怎么找从 pos 出发不断执行i lowbit(i)就行。以 n8、修改位置 3 为例c[3] 管 [3,3]要改下一个 i4c[4] 管 [1,4]要改下一个 i8c[8] 管 [1,8]要改再下一个 i16 超出范围停止。你会发现每次跳跃的跨度越来越大但总次数只有 O(log n)。这里有个非常容易踩的细节修改时判断越界的条件是i n因为 c 数组只开到 n不能往 c[n1] 后面乱写。2.4 前缀和查询反向走楼梯就能拼出答案查询前缀和时要从下标 x 反向累加。规则是先取 c[x] 的值然后执行x - lowbit(x)继续累加直到 x 变成 0。这个过程和修改正好相反原因也很直观c[x] 已经覆盖了 x-lowbit(x)1 到 x 这一段累加完成后下一个没覆盖到的区间终点恰好就是 x-lowbit(x)所以直接跳过去继续加。还是以 n8 为例查询前 7 个元素的和先加 c[7]覆盖 [7,7]然后 x 变成 6加 c[6]覆盖 [5,6]然后 x 变成 4加 c[4]覆盖 [1,4]x 变成 0 结束。三次累加刚好覆盖 1 到 7一个不多一个不少。这就是树状数组的本质它把整个前缀和拆成若干个长度是 2 的幂的块块与块之间无缝拼接。区间和查询自然就是sum(r) - sum(l-1)用的就是前缀和的可差分性。2.5 标准模板代码一份能直接抄的树状数组模板理解了上面这些模板其实已经呼之欲出了。下面这份是我惯用的写法注释都写在关键位置#include bits/stdc.h using namespace std; const int N 500010; int n; long long c[N]; int lowbit(int x) { return x -x; } void add(int pos, long long val) { for (int i pos; i n; i lowbit(i)) { c[i] val; } } long long sum(int pos) { long long res 0; for (int i pos; i 0; i - lowbit(i)) { res c[i]; } return res; } long long query(int l, int r) { return sum(r) - sum(l - 1); }初始化有两种常见方式。第一种是把 c 数组清零然后对原数组每个位置执行add(i, a[i])思路直接但复杂度是 O(n log n)。第二种更快读入时先把c[i] a[i]然后用j i lowbit(i)找到父节点把c[i]累加过去即if (j n) c[j] c[i];复杂度是 O(n)。我在比赛里通常直接用第一种因为 n 在 10^5 级别时差别不大但 n 到 10^6 以上O(n) 建树就很有必要了。3. 从单点到区间三个高频扩展模型3.1 差分数组先学会把区间改写成两次单点改树状数组原生只支持单点修改、前缀和查询。如果原数组 a 上要做区间 [l,r] 整体加 v直接上是做不到的。这时候引入差分数组 d其中 d[i]a[i]-a[i-1]事情就变简单了。对 a 的区间 [l,r] 整体加 v等价于对差分数组做两次单点修改d[l] 加 vd[r1] 减 v。反过来查询 a[x] 当前的值就是对 d 做前缀和 sum(x)。这个转化我第一次学的时候绕了好一会儿关键是想清楚差分数组的残差含义d 的前缀和能还原出 a 的当前值。于是树状数组改成维护 d原先的区间修改变成两个单点加原先的单点查询变成一次前缀和查询整体复杂度依然是 O(log n)。这个模型在必须处理大规模区间修改时特别常用。很多模板题就是专门练它的代码基本是把上一个小节的 add 和 sum 原样拿来用只是维护对象从 a 换成了 d。3.2 双树状数组区间修改、区间查询一起要再往上走一步是区间修改 区间查询同时出现。只维护一个差分数组能处理区间修改和单点查询但想直接查原数组的区间和就不够了。完整做法需要两个树状数组一个维护 d[i]另一个维护 d[i]*i。推导过程其实很漂亮。要求 a 的前缀和sum_a(x) sum_{i1}^{x} a[i] sum_{i1}^{x} sum_{j1}^{i} d[j] sum_{j1}^{x} d[j] * (x - j 1) (x1) * sum_d(x) - sum_di(x)这里的 sum_d(x) 是 d 的前缀和sum_di(x) 是 d[i]*i 的前缀和。所以开两个树状数组一个对 d[i] 做单点加一个对 d[i]*i 做单点加查询时分别取两个前缀和套公式即可。代码上只是把原来的 add 和 sum 各封装一下多传一个数组参数。这个模型最好亲手推一遍不要硬背公式因为背出来的公式很容易把 (x1) 和 i 的位置记反。3.3 二维树状数组把 lowbit 用到两个维度上树状数组的扩展能力比想象中强二维版本就是在 x、y 两个方向各做一次 lowbit 跳跃。修改 (x,y) 位置的值用两层循环外层ix; in; ilowbit(i)内层jy; jm; jlowbit(j)然后c[i][j] val。查询从 (1,1) 到 (x,y) 的子矩阵和同样两层循环方向改成i - lowbit(i)、j - lowbit(j)。求任意子矩阵和用二维容斥sum(x2,y2) - sum(x1-1,y2) - sum(x2,y1-1) sum(x1-1,y1-1)。二维树状数组的时间复杂度是 O(log n * log m)比暴力逐格累加快得多。但空间要特别注意如果直接开 n 乘 m 的二维数组n、m 到 10^4 级别就会爆内存实际题目里往往要做坐标离散化或者用离线 一维树状数组的思路替代。二维树状数组在偏序题和矩阵动态求和题里很常见属于会了能省很多事不会也能拿一维套一维硬啃下来的内容。3.4 离线与离散化配树状数组的常用辅助手段树状数组很多高级用法都离不开两个辅助手段离散化和离线处理。离散化针对的是值域过大、无法直接按下标开数组的情况。基本步骤是把原始数据复制一份排序去重然后用 lower_bound 找到每个元素在排序后数组中的排名。这样原本分散在 1e9 范围的值就被压缩到了 1..m 的连续区间树状数组的大小也能控制在可控范围内。离线处理则是把查询重新排序让它们满足某种偏序关系再用树状数组按顺序扫描维护答案。比如很多二维偏序题会把所有点按 x 排序然后边扫描边对 y 做计数。这套思路一旦熟练掌握很多看起来需要高级数据结构的问题实际用排序 树状数组就能解决而且代码量小、不容易错。4. 实战案例拆解四个典型场景一一过一遍4.1 单点修改 区间查询第一个场景就是最纯粹的模板给定 n 个数支持单点加和区间求和。输入里1 x y表示把第 x 个数加上 y2 x y表示查询 [x,y] 的和。我的写法和标准模板完全一致读入时直接add(i, 初始值)之后每条操作按类型分发。查询区间用query(l, r)不要真的写循环枚举。这道题是检验 lowbit 是否理解到位的试金石如果这个都一遍过说明树状数组基本操作已经建立起来了。4.2 区间修改 单点查询第二个场景换到差分模型初始数组 a操作一是把 [x,y] 区间每个数加 k操作二是求第 x 个数当前是多少。核心是把全局维护对象从 a 换成差分数组 d。对于区间加add(l, k)和add(r1, -k)各调用一次对于单点查询直接执行sum(x)拿到 d[1..x] 的和。有一个边界细节必须提当 r 恰好等于 n 时add(r1, -k)会往 n1 的位置写。因为后续查询最多查到 sum(n)这个越界写会导致数组下标越过声明范围出现诡异的 Runtime Error。所以树状数组的大小至少要保证是 n1或者在写模板时对 r1 单独判断一下。很多新手在这个点上排查很久方向往往都错了。4.3 逆序对统计把树状数组当计数器用逆序对的定义是 i j 且 a[i] a[j]。经典做法是归并排序但树状数组同样能统计而且思路更统一。先把所有值离散化成 1..m 的排名然后从右往左扫描原数组每遇到一个元素 x就在树状数组的下标 rank(x) 处加 1表示这个值已经出现过了同时累加答案时调用query(rank(x)-1)得到的是已经扫过的元素里比当前值小的数量。为什么从右往左扫因为右边已经扫过的元素在原数组中下标都大于当前 i如果它们的值比当前值小就构成一个逆序对。从左往右扫也可以只是要改成统计前面比当前值大的数量。离散化是必要步骤因为值域很大时不能直接按原值开树状数组。4.4 二维偏序与子矩阵求和树状数组在二维偏序问题里几乎是标配。典型问题给定 n 个点每个点有 (x,y) 两个属性问每个点左下方有多少个点。解决套路是先把所有点按 x 排序保证处理顺序满足后处理的点 x 更大然后用树状数组维护 y 值域的计数遍历时add(y, 1)查询sum(y-1)就是答案。这个套路本质上是在 x 维度排序在 y 维度做前缀计数。我碰到很多多维条件统计的题几乎都能抽象成这种一维排序 一维树状数组的问题。理解这道题之后你会发现自己对树状数组的认知从求和工具升级为计数工具很多以前觉得难的问题都会豁然开朗。5. 高频错误与调试技巧实录5.1 下标从 0 开始和 lowbit(0) 的死循环树状数组要求下标从 1 开始。如果直接用原数组的 a[0] 去 addlowbit(0) 永远是 0for (int i 0; i n; i 0)会直接死循环。我见过不止一次这种事故解决方式很简单读入后把下标加 1或者干脆声明一个虚拟位置让逻辑下标从 1 开始。另一个下标坑是 r1 越界前面已经说过时刻记得树状数组大小要比实际查询下标大 1。5.2 更新和查询方向写反怎么办add 的循环是i lowbit(i)sum 的循环是i - lowbit(i)。这个方向极其容易记混我自己的方法是记一句话修改向上找爹查询向左找块。 向上找爹是因为管辖范围更大的节点在更高位向左找块是因为要拼出完整前缀和只能往更小的下标移动。如果发现样例都对不上先检查这两个循环方向是不是整体反了。5.3 树状数组与线段树的选择决策实战里最纠结的往往就是这题能不能用树状数组。我总结了一个快速判断方式看这道题维护的信息是否可差分。可差分的信息包括和、异或、积、数量计数不可差分的信息包括最大值、最小值、gcd、区间覆盖后的结果。前者优先树状数组后者上线段树。信息类型是否可差分推荐结构区间和、区间异或可以树状数组计数、频率可以树状数组区间最大值、最小值不可以线段树gcd、区间覆盖通常不可以线段树另外如果题目强制要求在线区间赋值也不要强行树状数组老老实实写线段树。5.4 我常用的对拍调试套路分享几个我经常用的调试方法。第一写一个 O(n^2) 的暴力程序做对拍随机生成小规模数据一旦两边答案不一致立刻缩小数据范围定位错误。第二把 c 数组在关键操作后打印出来手动验证 c[i] 是否真的等于对应区间的和。第三多测用例一定要记得把树状数组清零最快的办法是fill(c, c n 1, 0)不要自信地以为下一次读入会自动覆盖干净。5.5 一份快速自查清单最后放一个每次提交前我会在脑子里过一遍的清单下标是否已经全部改成从 1 开始add 循环条件是i nsum 循环条件是i 0区间查询用的是sum(r) - sum(l-1)不是sum(r) - sum(l)差分时r1是否可能越界数组开够了吗多测样例有没有清空 c 数组离散化之后用的是 rank不是原值这些检查点看起来琐碎但实际救过我很多次。一个人在紧张状态下最容易出的错往往不是推导问题而是这些基础细节。我把这套流程跑顺之后写树状数组的题基本不太需要调试大多数情况下都是一遍过。这也是我在 2026 年 1 月 12 日这次总结里最想强调的事树状数组的模板很短难不在写而在边界处理和模型转化。如果你今天准备开始学建议先手推一遍 lowbit再照着模板敲三道不同模型的题效果会比只看完文章好得多。
