最近整理数据结构笔记时顺手把编号20260112这页留给了“树状数组”——这并不只是一个写着玩的编号算是我给自己定的一个复习节点。树状数组简单记作 BIT也叫 Fenwick Tree在算法竞赛和日常开发里的出场率都极高核心能力概括起来很朴素支持单点修改和前缀和查询并且两个操作都控制在 O(logn) 的时间复杂度内。花这么大力气单独写一篇总结是因为它的代码量虽然只有二十多行但很多初学者卡在“为什么树状数组要长这样”而不是“模板怎么背”。这篇笔记面向的对象就是那些想真正把 BIT 吃透的人无论你是在备考算法题还是在准备面试手撕代码都可以直接参考。先说一句我写这篇总结的原则是每个循环、每个边界都讲清楚原因而不是丢给你一段不知道哪里抄来的模板。理解完以后你会发现它并不神秘本质上就是“用二进制把数组拆成许多小块再按块维护信息”。1. 为什么一个数据结构值得单独总结它解决的是一类“在线”前缀问题在动手看代码前先回到最原始的问题。假设你要维护一个长度为 n 的数组 a支持两类操作一是把某个位置 i 增加 delta二是查询前若干个位置的总和。如果操作是一锤子买卖那直接算前缀和数组就行初始化 O(n)查询 O(1)。但现实场景往往是一边修改一边查询这就是“在线”的前缀统计问题。原始暴力和前缀和数组分别走了一个极端原始数组做单点修改是 O(1)但查询前缀和只能从头扫到尾O(n)反过来存完整前缀和会让查询变快但每次改一个点后面所有前缀和都要同步更新又退化成 O(n)。数据量一上来无论偏向哪一边都会很尴尬。题目甩给你十万个操作的时候O(n) 的操作次数会立刻爆炸。树状数组最高明的地方就是它两边只付出了 O(logn)单点修改走一条短链前缀查询拆成若干小块。它不存完整的原始数组也不存所有前缀和而是把整个序列切成一堆长度按二进制规律变化的“小计”分散放在编号固定的数组 slot 里。我把三种思路摆在一个表里看得更直观一些方案单点修改前缀查询额外空间原始数组O(1)O(n)O(n)前缀和数组O(n)O(1)O(n)树状数组O(logn)O(logn)O(n)这类场景在真实世界里并不少。比如直播间的在线人数每隔几秒就有观众进场和离开某个人进来只影响一个点数但要随时知道某一时刻之前累计有多少人又比如电商订单的累计金额一张订单改了金额后台希望立刻算出当天前几个小时的累计营收。这类需求本质都是“单点变动 前缀聚合”树状数组的名字里虽然有“数组”但在这些场景里它就是一层轻巧的多级缓存。1.1 为什么前缀和数组做不到“轻量组合”也许你会想那我把数组按块分组比如分 sqrt(n) 块每块维护一个块内和查询跨块的时候把完整块的和直接拿来用这不也行吗这确实是分块优化的思路查询和修改能做到 O(sqrt(n))。但树状数组的拆分粒度更细它不是固定块大小而是按二进制的 lowbit 动态切块。这样前缀查询需要合并的块数从 sqrt(n) 级别降到了二进制位个数级别也就是 O(logn)。真工程和竞赛里O(sqrt(n)) 在十万级数据量下勉强能用到了百万甚至更大log 的优越性就非常明显。另外前缀和数组还有一个隐藏问题如果维护的数据类型支持“叠加”但也支持“撤销”那么前缀和数组可以快速反映单点修改吗并不能因为修改一个点要影响它后面所有前缀数组元素这个更新是连续的一段没法跳过。树状数组的单点更新路径则是一条条跳跃的链子虽然也是若干个位置但这些位置的个数约为 logn 个远远少于一整段。2. 从二进制角度看树状数组的骨干lowbit 区间划分理解了它想解决什么问题剩下最关键的就是搞清楚“一块小计到底覆盖了哪一段”。这里必须先认识一个函数 lowbit(x)它表示正整数 x 在二进制表示下最低位的 1 对应的值。比如 6 的二进制是 110最低位 1 对应的数值是 2所以 lowbit(6) 2。写代码时一行就能算出来int lowbit(int x) { return x -x; }为什么x -x能求出这个值因为在计算机的补码表示里-x等于把 x 取反再加一。x 的最低位 1 右边全是 0取反后这一位变成 0右边变成 1再加一后右边重新变回 0只有这一个低位 1 被保留并且重新进位到原位置。所以 x 和 -x 做按位与之后得到的结果恰好只有最低位那个 1 是 1其他位全为 0。这个技巧非常经典直到今天依然没有更简短的替代写法。树状数组的维护数组我习惯叫tree它每一个下标 i 并不直接存 a[i]而是存储原数组中区间[i - lowbit(i) 1, i]的和。这句话是整个 BIT 的基石下标 i 管多长的一段完全由 i 的二进制最低位决定。为了看得更清楚我把长度为 16 的序列中前 8 个下标对应的覆盖区间列出来ilowbit(i)tree[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]从这张表里能明显看到规律下标为偶数的位置往往覆盖更长的区间下标为奇数则基本只覆盖自己单个点因为奇数的二进制最低位一定是 1。这里最重要的一个特性是所有长度都是 2 的整数次幂而且每个树状数组节点覆盖的右端点就是它自己的下标左端点则是右端点减去 lowbit 再加一。2.1 前缀查询为什么能拆成若干“完整块”现在来看看查询前缀和。假设我要查询前 13 个数的和13 的二进制是 1101。按刚才的区间划分我可以先取 tree[13]它覆盖 [13,13]剩下需要前 12 个数于是把下标变成 13 - lowbit(13) 12tree[12] 覆盖 [9,12]再往前12 - lowbit(12) 8tree[8] 覆盖 [1,8]。整个过程对应的下标路径是 13 → 12 → 8一共三段刚好把 [1,13] 完整切成 [13,13]、[9,12]、[1,8]没有重叠也没有遗漏。这个现象和二进制的关系非常直观13 的二进制 1101 其实就是在告诉你这个前缀可以拆成三个长度分别为 1、4、8 的段。把二进制表示里从低到高的每一个 1 都“抠”出来每抠掉一个 1就找到一段已经算好的树状数组值。因为二进制里 1 的个数最多只有 logn 个所以前缀查询需要的段数也被限制在 logn 个这就是复杂度 O(logn) 的来源。既然每次查询都只是把若干个现成的“小计”相加那速度自然很快。同理单点修改要更新的位置也反过来下标 i 更新后由它组成的所有上层覆盖区间都要同步变化。从下标 i 出发不断执行i lowbit(i)就能找到所有“右端点不小于 i 且区间包含 i”的父级节点。比如修改位置 3它会影响到 tree[3]、tree[4]、tree[8]、tree[16]……这些节点覆盖的区间都包含位置 3。沿着这条路径向上走走的步数同样是 logn 级别。lowbit 构成了整个树状数组的骨架。它为什么能同时兼顾“查询时拆块”和“更新时向上合并”是因为任意正整数都可以唯一表示成若干个 different 的二进制位之和这两套路径本质上是同一个二进制拆数的过程查询时从某个下标不断减 lowbit更新时不断加 lowbit。理解到这一层后面写任何变种代码都不会觉得是在背模板。3. 三种写法拆解单点更新、前缀查询、O(n) 建树现在可以给出最标准的一维写法。这是我在实际比赛和日常代码里反复使用的版本没有花哨优化胜在稳定和容易查错const int N 200010; int n; long long tree[N]; void add(int idx, long long delta) { for (; idx n; idx idx -idx) { tree[idx] delta; } } long long query(int idx) { long long res 0; for (; idx 0; idx - idx -idx) { res tree[idx]; } return res; }add 函数里循环起始点是当前需要修改的位置每走一步都用idx (idx -idx)跳到包含它的下一个上级节点。这样所有覆盖了 idx 的树状数组节点都会被同步加上 delta。query 函数则是反向操作从idx开始不断去掉最低位的 1把这些区间小计累加起来直到 idx 变成 0。这里有几处新手特别容易踩的细节。第一个是数组下标必须从 1 开始不能从 0 开始因为lowbit(0) 0查询函数会在idx 0时陷入死循环。所以不管是原始数组还是树状数组我都统一把下标偏移成从 1 开始。第二个是 add 的循环条件必须是idx n不能写成 n否则最后一个位置对应的节点更新不到query 的循环条件则不能写成idx 0因为到了 0 以后它会死循环。第三个是 res 和 delta 的类型我建议直接用 long long因为前缀和很容易超出 int 能表示的范围。3.1 初始化不是只能暴力插入O(n) 建树也很简单最直观的建树方式是把原始数组 a[1..n] 逐个调用 add(i, a[i])复杂度是 O(nlogn)。虽然大多数题目 n 只有十万级这个建树成本完全可以接受但既然要做总结我建议顺手掌握 O(n) 的线性建树法。原理并不复杂每个树状数组节点 tree[i] 的组成是它覆盖的原始区间之和而这个区间可以拆成它自己和它的直接子区间。如果我们从下标 1 到 n 扫描把当前节点累积的值“盖上”到它的父亲节点上那么扫描到某个节点时它手里已经收集齐了原数组的值和所有子区间的贡献。代码可以写成这样for (int i 1; i n; i) { tree[i] a[i]; int father i (i -i); if (father n) { tree[father] tree[i]; } }验证一下比如 a [1,2,3,4]。循环到 i1 时tree[1] 变成 1father 是 2于是 tree[2] 从 0 变成 1循环到 i2 时tree[2] 先加上 a[2] 变成 3再把 3 加到 tree[4]循环到 i3 时tree[3] 变成 3father 是 4所以 tree[4] 再加上 3循环到 i4 时tree[4] 加上 a[4] 变成 7。最后 tree[4] 1234正确。整个扫描过程每个节点只处理一次所以是严格的 O(n)。如果你的树状数组平时从空数组开始反复 add也可以用另一种直观写法对每个 i直接从i - lowbit(i) 1扫到 i把 a[j] 相加放进 tree[i]。这个办法理解起来最自然可惜复杂度是 O(nlogn)适合作为初学时的验证代码不适合大规模初始化。3.2 二维树状数组把一维循环直接嵌套二维 BIT 是高频扩展点代码量依然不大。你需要一个二维数组 tree然后单点修改和前缀查询都变成两重循环内层完全照搬一维的 lowbit 逻辑void add2d(int x, int y, int delta) { for (int i x; i n; i i -i) { for (int j y; j m; j j -j) { tree2d[i][j] delta; } } } long long query2d(int x, int y) { long long res 0; for (int i x; i 0; i - i -i) { for (int j y; j 0; j - j -j) { res tree2d[i][j]; } } return res; }二维 BIT 维护的是二维前缀和。求子矩阵(x1,y1)到(x2,y2)的和时用四个二维前缀和做容斥即可query2d(x2,y2) - query2d(x1-1,y2) - query2d(x2,y1-1) query2d(x1-1,y1-1)。这个结构在图像处理、数据热力图等需要频繁更新单元格并查询矩形累计量的场景里很实用。只要你理解了 lowbit 骨架一维扩展到二维只需要加一层循环没有新概念。4. 从套路到题型树状数组为什么能渗透进一大类题树状数组能解决的不只是“单点修改 前缀和”这一个模板。之所以它应用范围这么广是因为很多看起来完全不是这个模样的题都能通过转化变成“单点更新 前缀统计”。掌握这些经典套路往往比多背几十道题有用得多。第一种套路是差分。差分的思想很简单给原数组区间 [l, r] 整体加上 v等价于在差分数组里d[l] vd[r1] - v。这样一来区间加变成了两个单点修改查询某个位置 a[x] 变成了求差分数组的前缀和。于是“区间加、单点查询”这类问题直接被 BIT 收编。甚至“区间加、区间求和”也能做你需要同时维护两个 BIT一个维护差分数组 d[i]另一个维护 d[i] * (i-1)公式推导完成后仍只有两次单点更新和两次前缀查询。差分与 BIT 的组合本质上就是把“连续一段的变化”改写成“两个端点的变化”非常优雅。第二种套路是权值计分。当问题是“统计有多少个数比当前值大”时你可以把值域作为 BIT 的下标用 BIT 维护每个数值出现的次数。每次插入一个新的数 x 时先查询当前已经插入的数中有多少个落在某个前缀范围内再对 x 这个位置做 add(x, 1)。这个玩法最典型的例子是逆序对计算。把原序列按顺序扫描每次统计“已经出现过的且数值比 x 大的数的个数”累加的结果就是逆序对数。由于值域可能很大通常需要先离散化一下给每个不同的数分配一个紧凑的排名BIT 数组的大小就不再依赖原始值域了。// 离散化 vectorint vals a; sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); long long inv 0; for (int x : a) { int id lower_bound(vals.begin(), vals.end(), x) - vals.begin() 1; // 已插入的、值大于 x 的数量 inv (long long)query(n) - query(id); add(id, 1); }第三种套路是第 k 小/第 k 大查询。既然 BIT 是一棵按二进制分块的树那它天然支持“在累计频率里二分”。想知道当前所有数中第 k 小的值可以用一个类似二进制倍增的写法从大到小枚举步长尝试累加树状数组节点int maxLog 1; while ((maxLog 1) n) maxLog 1; int kth(int k) { int pos 0; for (int step maxLog; step 1; step 1) { int nxt pos step; if (nxt n tree[nxt] k) { k - tree[nxt]; pos nxt; } } return pos 1; }这段代码我是按 n 的最大二次幂来枚举 step 的。如果第 k 小的值在权值 BIT 上查询为 pos1那么 tree[nxt] 正好是“前 nxt 个频率的和”。整个查找过程从大到小逼近答案复杂度 O(logn)。很多人会用线段树二分求第 k 小但既然 BIT 天然是二进制结构用这个写法显然更短更快。除了这些经典套路树状数组还可以处理动态排名、流式数据的前缀截断、滑动窗口内的频率统计等。你会发现 BIT 在这些题里很多时候不是“主角算法”而是“基础设施”基础数据结构负责维护信息你负责设计信息的维护方式和查询公式。这种习惯非常重要真正的高手眼里树状数组就像一把多用途扳手碰上合适的问题直接拧上去。5. 和线段树的边界什么时候别留恋漂亮代码说到树状数组就绕不开线段树。两者都能把区间操作做到 O(logn)于是很多人在选型时纠结。我的建议很简单能用 BIT 绝不上线段树但该上线段树的时候也别硬撑。为什么这么说我拿一份亲身体会总结对比表来展示角度树状数组线段树代码量很简短核心函数十几个字符通常需要建树、更新、查询、懒标记等量大调试难度容易出错位置明显写错一个区间合并逻辑就可能整套崩空间O(n)常数小O(4n)维护懒标记后更大区间最值只能处理部分特殊前缀最值通用性弱原生支持任意区间最值区间修改靠差分/数学推导变通原生支持懒标记多维扩展嵌套循环代码仍短树套树复杂度很高时间常数很小相对较大为什么 BIT 这么简洁因为它的本质建立在“区间信息可以相减”的基础上也就是前缀和可以用两个端点做差。如果问题需要的统计量支持反向运算求和、求异或、求积等BIT 都能轻松处理但如果是区间最大值这种不可逆统计BIT 就很别扭。虽然可以设计出支持前缀最大值且只增不改的变体但任意区间查询最值时线段树才是正解。另一个判断标准是区间修改的复杂性。BIT 用差分可以优雅地解决区间加和单点查询解决区间加和区间求和也需要两个 BIT 做推导但如果要“区间赋值、区间求和”BIT 就很难受这时候线段树的懒标记是天生为它准备的。区间翻转、区间覆盖这类问题线段树的优势更是无可替代。所以选型时先问两件事第一统计量可不可逆第二修改操作是不是只在端点级别。如果两个答案都是肯定放心用 BIT。我在实际项目里还遇到过另一种情况题目本身可以用线段树但线段树的常数在几十万次操作下明显偏大。同样跑一组数据BIT 可能三秒内出结果线段树却要接近超时。这时即便线段树能支持更多操作我也会优先选择 BIT除非题目必须用到区间最值或懒标记。树状数组“漂亮”的不只是代码更是它极低的常数这才是它长期在竞赛数据结构中不被淘汰的真正原因。6. 我在实际使用中反复踩到的坑与避坑建议最后写一部分自查清单都是我真实踩过、或者帮别人调代码时反复看到的坑。每一条背后都是血的教训。第一循环条件“差一个等于号”。add 函数里写成idx n看似差不多实际上当 idx 正好等于 n 时最后一次更新不会执行导致最后一个位置始终缺席。正确写法是idx n。类似的初始化 O(n) 建树时判断父亲节点也要带等于号if (father n)。第二查询函数的终止条件。query 里如果写成idx 0程序会在 idx0 时因为idx - lowbit(0)永远得不到 0 而陷入死循环。想清楚 lowbit(0) 等于 0 这个事实终止条件自然写idx 0。第三下标从 1 开始还是从 0 开始。原始数组用 0-based 很顺手但 BIT 的树状数组下标是从 1 开始的。转换不一致会带来一系列越界和漏算。我的习惯是读入数据后把 a[i] 存到 index i1 的位置所有业务逻辑统一用 1-based。第四int 溢出。这个坑尤其隐蔽单点增加虽然只是一个数但所有包含它的节点都会同步累加几万次累加下来tree 里的数值很可能超过 int 范围。前缀查询的结果也一样。我从一开始就建议 BIT 的 value 类型用 long long不要等 WA 了才回头改类型改完整段代码的代价更高。第五离散化去重后的“边界”问题。做逆序对这类题目时如果原数组有大量重复值unique去重后你需要用 lower_bound 把同一个值映射到同一个 id。统计“严格大于当前值”和“大于等于当前值”时查询公式略有不同别混淆。例如统计逆序对时通常用当前 id 之后的数量如果有重复值那两个相等的数不应算作逆序对所以依赖去重后 id 的相对次序时思路要始终保持一致。第六不要把区间最值硬凹进 BIT。很多题目在求区间最小值你搜索一圈可能看到“BIT 支持前缀最值”的说法就顺手套上去结果查询任意区间时发现前缀最值无法做差。BIT 求任意区间最值的通用性很差要么加辅助数组要么直接换线段树。这个坑特别容易让新手浪费大量时间。第七写完模板别急着交先对拍。我的习惯是用一个随机小数据生成器把暴力前缀和结果和 BIT 结果逐项比较操作几百次以后再测边界 n1、n2、n 很大这些情况。对拍的代码量没多少但它能在你写错任何一个边界时立刻亮红灯省下的调试时间是翻倍的。尤其是 kth 函数里步长的初始值如果最高位不够大会直接漏掉一半值域这种错误肉眼很难发现对拍一秒钟就能暴露。写到这里这页编号 20260112 的树状数组总结就算是完整闭环了。结合我自己的经验最想传递的一条建议是一维 BIT 的几个核心函数add、query、O(n) 建树、kth值得你练到能默写的程度因为它不只是模板更是你理解“二进制拆数 区间覆盖”这个思想的最小骨架。遇到新的统计题先问自己能不能转化成前缀信息能就往 BIT 的方向靠不能再去动线段树。保持这个思维习惯很多算法题会瞬间变得通透许多。