写在前面本文面向算法竞赛初学者从零开始用最通俗的语言和图解带你彻底搞懂树状数组。全文约8000 字建议收藏边看边在纸上画图。 目录一、引言我们遇到了什么问题二、树状数组是什么三、核心概念lowbit 是个什么魔法3.1 定义3.2 直观理解3.3 为什么叫 lowbit四、树状数组的结构长什么样第一张图管辖范围俯视图看清tree和a的真实关系算法跳跃动态图看清lowbit是怎么带路的1. 更新操作add(3)—— 向上合并2. 查询操作sum(7)—— 向左拆分五、两个核心操作5.1 单点更新add(pos, delta)5.2 前缀查询sum(pos)六、完整代码膜拜七、经典应用场景7.1 场景一单点更新区间求和7.2 场景二区间更新单点查询7.3 场景三区间更新区间查询7.4 场景四求逆序对八、典型例题精讲例题一LeetCode 315 变体 —— 统计右侧大于当前元素的个数例题二洛谷 P1908 —— 逆序对例题三动态维护前缀最大值非求和九、复杂度与优缺点时间复杂度空间复杂度优点缺点十、练习题推荐结语一、引言我们遇到了什么问题假设你有一个长度为n的整数数组a[]现在需要频繁执行两类操作操作 A修改某个位置的值单点更新操作 B求前k个数的和前缀查询或区间[l, r]的和如果直接用普通数组修改O(1)但求和需要遍历O(n)。如果维护前缀和数组求和O(1)但每次修改都要更新后续所有前缀和O(n)。当n和操作次数都达到10^5以上时O(n^2)必然超时。我们需要一种数据结构让更新和查询都变得很快最好都是O(log n)。树状数组就是为解决此类问题而生的精巧数据结构。二、树状数组是什么树状数组英文名Fenwick Tree也叫Binary Indexed TreeBIT是一种用于高效维护前缀信息的数据结构。它不是一个真正的树而是一个数组通过巧妙地利用二进制下标来模拟树形关系。它支持单点更新add(i, delta)将位置i的值增加delta时间复杂度O(log n)。前缀查询sum(i)求前i个元素的和时间复杂度O(log n)。区间和可以用前缀和相减得到sum(r) - sum(l-1)。 与线段树的区别树状数组能解决的问题有限主要针对可加性信息如和、异或但代码极短、常数小、不易写错。线段树是全能选手但代码长。能用树状数组时优先用它。三、核心概念lowbit 是个什么魔法树状数组的灵魂是lowbit运算。3.1 定义lowbit(x)返回x的二进制表示中最低位的 1 及其后面所有的 0所组成的数值。计算公式Cintlowbit(intx){returnx-x;}什么你说你不知道怎么把一个int取相反数可以补充一下csapp中补码相关的知识大致就是取反就是将每一位取反再1比如0001的相反数就是11101 1111即1变成了-1为啥是这样因为补码中第一个bit是符号位 1111 -23222120-13.2 直观理解十进制x二进制lowbit(x)说明100011最低位1在第0位200102最低位1在第1位300111最低位1还是在第0位401004最低位1在第2位501011601102二进制 110最低位1在1位701111810008最低位1在第3位你会发现lowbit(x)恰好是x二进制中最右边 1 的权值。3.3 为什么叫 lowbit因为它取的是二进制中最低位Least Significant Bit的值。四、树状数组的结构长什么样我们用tree[]来表示树状数组下标从1开始抛弃 0。核心规则tree[i]负责维护原数组区间(i - lowbit(i), i]的和即a[i - lowbit(i) 1]到a[i]。我们以n 8为例列出每个tree[i]的管辖范围i二进制lowbit(i)管辖范围管几个数100011[1, 1]1200102[1, 2]2300111[3, 3]1401004[1, 4]4501011[5, 5]1601102[5, 6]2701111[7, 7]1810008[1, 8]8第一张图管辖范围俯视图看清tree和a的真实关系这张图横向展开让你一眼看穿每个tree[i]到底“管”了a里的哪几个数。数组 a: a1 a2 a3 a4 a5 a6 a7 a8 ─────┬─────┬─────┬─────┬─────┬─────┬─────┬───── tree[1] [1] tree[2] [1 2] tree[3] [3] tree[4] [1 2 3 4] tree[5] [5] tree[6] [5 6] tree[7] [7] tree[8] [1 2 3 4 5 6 7 8]看这张图的重点tree[2]管[1,2]而tree[3]只管[3]。它们只是平级关系谁也不包含谁。一个格子长度 lowbit(i)。比如tree[6]二进制110lowbit2所以它横跨 2 格管a5,a6。总结规律tree[i]的区间长度 lowbit(i)起点是i - lowbit(i) 1。算法跳跃动态图看清lowbit是怎么带路的这张图展示更新和查询时下标是怎么“跳”的。1. 更新操作add(3)—— 向上合并当你给a3加了一个数需要顺着箭头往右上跳更新包含它的所有大区间。跳跃路径: 3 ───(1)─── 4 ───(4)─── 8 ───(8)─── 16 (超出,停止) │ │ │ ▼ ▼ ▼ 更新 更新 更新 tree[3] tree[4] tree[8] (管a3) (管a1~a4) (管a1~a8)背后的二进制3(0011) lowbit(3)1→4(0100)4(0100) lowbit(4)4→8(1000)2. 查询操作sum(7)—— 向左拆分当你查询前 7 个数的和需要把[1,7]拆成几块互不重叠的区间拼起来。跳跃路径: 7 ───(-1)─── 6 ───(-2)─── 4 ───(-4)─── 0 (停止) │ │ │ ▼ ▼ ▼ 累加 累加 累加 tree[7] tree[6] tree[4] (只管a7) (管a5~a6) (管a1~a4) 合并结果: tree[7] tree[6] tree[4] a7 (a5a6) (a1~a4) a1~a7背后的二进制7(0111) -lowbit(7)6→6(0110)6(0110) -lowbit(6)4→4(0100)4(0011) -lowbit(4)0→0(0000)01停止五、两个核心操作5.1 单点更新add(pos, delta)目的将原数组a[pos]增加delta并更新所有包含pos的tree[]节点。过程从i pos开始。将tree[i] delta。i lowbit(i)跳到父节点。重复 2-3直到i n。举例更新pos 3n 8跳跃路径3 → 4 → 8。因为a3之和这三个tree上的node有关只修改了 3 个节点却保证所有包含 a[3] 的区间都被更新。5.2 前缀查询sum(pos)目的求原数组a[1] a[2] ... a[pos]的和。过程从i pos开始。累加res tree[i]。i - lowbit(i)跳到前一个不相交的区间。重复 2-3直到i 0。举例查询前 7 个数的和跳跃路径7 → 6 → 4 → 0。图示用大括号表示每次累加的区间下标: 1 2 3 4 5 6 7 8 |---|---|---|---|---|---|---|---| 累加 tree[7] : 覆盖 [7] 累加 tree[6] : 覆盖 [5,6] 累加 tree[4] : 覆盖 [1,4] 合并结果: [1,4] [5,6] [7] [1,7] 完全覆盖为什么路径是 7→6→4因为7 111₂lowbit(7)1减去得110₂6lowbit(6)2减去得100₂4lowbit(4)4减去得0。其实就是不断去掉二进制最右边的1。这样每次加上对应范围的前缀和凑成全部前缀和六、完整代码膜拜这是一个封装好、可直接复用的模板。#includevectorusingnamespacestd;classFenwick{private:intn;vectorinttree;// 树状数组下标从1开始intlowbit(intx){returnx-x;}public:Fenwick(intn):n(n),tree(n1,0){}// 单点更新在 pos 位置增加 deltavoidadd(intpos,intdelta){for(intipos;in;ilowbit(i))tree[i]delta;}// 前缀查询求 [1, pos] 的和intsum(intpos){intres0;for(intipos;i0;i-lowbit(i))restree[i];returnres;}// 区间查询求 [l, r] 的和intrangeSum(intl,intr){returnsum(r)-sum(l-1);}};使用示例Fenwickbit(10);bit.add(3,5);// a[3] 5bit.add(5,2);// a[5] 2coutbit.sum(4);// 输出前4个元素的和假设其他都是0则5coutbit.rangeSum(3,5);// 输出 a[3]a[4]a[5] 5027–请完成洛谷 P3374 【模板】树状数组 14七、经典应用场景7.1 场景一单点更新区间求和这是最基础的应用上面模板已经实现。常用于动态维护前缀和或区间和。7.2 场景二区间更新单点查询使用差分数组配合树状数组。原理设原数组为a[]差分数组d[i] a[i] - a[i-1]a[0]0。对区间[l, r]统一加v只需add(l, v)和add(r1, -v)。查询a[pos]的值就是求d[1] ... d[pos]即sum(pos)。代码片段// 区间 [l, r] 加 vbit.add(l,v);bit.add(r1,-v);// 查询 pos 位置的值longlongvalbit.sum(pos);7.3 场景三区间更新区间查询维护两个树状数组bit1和bit2通过差分推导出公式。公式略去推导区间[l, r]加vbit1.add(l, v); bit1.add(r1, -v);bit2.add(l, v*(l-1)); bit2.add(r1, -v*r);前缀和sum(pos)bit1.sum(pos)*pos - bit2.sum(pos)。区间和 sum(r) - sum(l-1)。7.4 场景四求逆序对问题给定一个数组求有多少对(i, j)满足i j且a[i] a[j]。思路离散化压缩值域。从右往左遍历数组每次查询当前已遍历元素中小于等于当前值的个数即sum(idx)用已遍历总数减去它就是右侧小于当前值的个数累加到答案。将当前值加入树状数组。代码核心// 离散化vectorlonglongsortednums;sort(sorted.begin(),sorted.end());sorted.erase(unique(sorted.begin(),sorted.end()),sorted.end());Fenwickbit(sorted.size());longlongans0;for(intin-1;i0;--i){intidxlower_bound(sorted.begin(),sorted.end(),nums[i])-sorted.begin()intidxlower_bound(sorted.begin(),sorted.end(),nums[i])-sorted.begin()1;// 这行代码详解// 1. sorted 是 nums 排序去重后的数组离散化后的值域// 2. lower_bound(sorted.begin(), sorted.end(), nums[i]) 返回第一个 nums[i] 的迭代器// 3. 减去 sorted.begin() 得到在 sorted 数组中的下标从0开始// 4. 1 是因为树状数组下标从1开始避免0下标// 最终 idx 表示 nums[i] 在离散化后的排名1-based1;// 右侧小于 nums[i] 的个数 已遍历总数 - sum(idx)ans(n-i-1)-bit.sum(idx);bit.add(idx,1);}八、典型例题精讲例题一LeetCode 315 变体 —— 统计右侧大于当前元素的个数题目给定数组nums返回count数组其中count[i]是nums[i]右侧大于nums[i]的元素个数。解法与逆序对类似从右往左用树状数组统计频数用总数减去当前值的个数即为大于的个数。完整代码CclassSolution{public:classFenwickTree{private:intn;vectorintTree;intlowbit(inti){returni(-i);}public:FenwickTree(intn):n(n),Tree(n1,0){}voidadd(intidx,intdelta){while(idxn){Tree[idx]delta;idxlowbit(idx);}}intsum(intpos){intres0;while(pos0){resTree[pos];pos-lowbit(pos);}returnres;}};vectorintcountSmaller(vectorintnums){intnnums.size();vectorintans(n,0);vectorintsortednums;sort(sorted.begin(),sorted.end());sorted.erase(unique(sorted.begin(),sorted.end()),sorted.end());FenwickTreeft(sorted.size());for(intin-1;i0;--i){//将数字映射为下标比如1 2 5 6 5 映射为3intidxlower_bound(sorted.begin(),sorted.end(),nums[i])-sorted.begin()1;ans[i]ft.sum(idx-1);//求求前缀和为的时候啥也没有ft.add(idx,1);//将当前的数加入相对序列里面因为映射过去就是1下一个是6对应的idx是4前缀和就是1因为前面吧6右侧的1这个较小的数给加到树状数组对应的位置上去了给对应位置赋予了一个数字就可以用前缀和统计右侧比它小的是数字的数量}returnans;}};例题二洛谷 P1908 —— 逆序对模板题直接用上面逆序对的方法即可。例题三动态维护前缀最大值非求和树状数组不仅可以维护和还可以维护最大值、最小值等可合并且满足可减性的信息如最大值不具备可减性但可以维护前缀最大值。只需将add中的改为maxsum改为查询最大值但注意此时只支持单点更新只能增大和前缀最大值查询。九、复杂度与优缺点时间复杂度单点更新O(log n)前缀查询O(log n)区间查询O(log n)两次前缀查询空间复杂度O(n)仅需要一个n1的数组。优点✅ 代码极短不易出错✅ 常数小运行速度快✅ 空间省只开一个数组缺点❌ 只能处理可加性的信息和、异或、积不能处理最值除非特殊限制❌ 区间修改、区间查询实现较复杂需多个BIT❌ 无法支持区间赋值等复杂操作十、练习题推荐序号题目名称来源考察点1LeetCode 307. 区域和检索 - 数组可修改单点更新区间查询2LeetCode 315. 计算右侧小于当前元素的个数离散化逆序对3LeetCode 493. 翻转对变种逆序对两倍关系4洛谷 P3374 【模板】树状数组 1单点更新区间查询5洛谷 P3368 【模板】树状数组 2区间更新单点查询6HDU 1166 敌兵布阵基础单点更新区间求和建议顺序先做模板题P3374、P3368再刷 LeetCode 上的相关题目。结语树状数组虽然小巧但背后蕴含的二进制思想十分深刻。掌握它不仅能提升你的算法能力更能让你在面对“数据动态维护”问题时多一把利器。如果你觉得本文对你有帮助请点赞、收藏也欢迎在评论区留下你的问题或建议。下一篇我们将进军线段树敬请期待本文代码均已测试通过所有模板可直接复制使用。✍️ 写作不易转载注明出处。完