信息学竞赛数据结构——树状数组

教学目录树状数组定义区间长度前驱和后继查询前缀和点更新查询区间和树状数组代码实现算法分析课程小结一、树状数组定义知识点树状数组的引入给定一个长度为 n 的数组 a需要支持两种操作将第 x 个元素的值增加 v。查询区间 [1, x] 的前缀和。若使用普通数组点更新为 O(1)但前缀和查询为 O(n)无法满足大规模数据的要求。树状数组的定义树状数组Fenwick Tree / Binary Indexed Tree简称 BIT是一种用于高效维护数组前缀和的数据结构。它能在 O(log n) 的时间内完成单点更新和前缀和查询。核心思想将原始数组的下标按照二进制表示进行分组每个节点 c[x] 管理原始数组中一段连续区间的和。通过二进制最低位的 1 来确定每个节点管理的区间范围。树状结构树状数组本质上是一棵由数组下标二进制低位 1 决定父子关系的多叉树。每个节点 c[x] 的父节点是 c[x lowbit(x)]。二、区间长度知识点lowbit 函数lowbit(x) 表示 x 的二进制表示中最低位的 1 所对应的数值。例如lowbit(6) lowbit(110₂) 2₁₀ 2。lowbit(8) lowbit(1000₂) 8₁₀ 8。lowbit 的计算公式lowbit(x) x -x。在计算机中负数以补码形式存储-x ~x 1因此 x -x 恰好能提取 x 最低位的 1。区间长度节点 c[x] 管理的区间长度为 lowbit(x)。即节点 c[x] 维护的是原数组区间 [x - lowbit(x) 1, x] 中所有元素的和。举例说明当 x 6 时lowbit(6) 2则 c[6] 管理区间 [5, 6] 的和。当 x 8 时lowbit(8) 8则 c[8] 管理区间 [1, 8] 的和。示例lowbit 取值表x二进制lowbit(x)管理区间111[1, 1]2102[1, 2]3111[3, 3]41004[1, 4]51011[5, 5]61102[5, 6]71111[7, 7]810008[1, 8]三、前驱和后继知识点前驱节点在树状数组中节点 x 的前驱为 x - lowbit(x)。前驱节点对应的是查询前缀和时当前节点管辖区间之前紧邻的区间的起点。后继节点在树状数组中节点 x 的后继为 x lowbit(x)。后继节点对应的是单点更新时需要向上更新所有覆盖了位置 x 的父节点。前驱的作用查询前缀和 sum(x) 时每次迭代都将当前节点 x 更新为其前驱 x - lowbit(x)。这样可以快速跳过已累加的区间跳转到下一个需要累加的区间。后继的作用单点更新 add(x, v) 时每次迭代都将当前节点 x 更新为其后继 x lowbit(x)。这样可以自底向上更新所有包含位置 x 的节点。示例x 6 的前驱和后继节点 xlowbit(x)前驱 x - lowbit(x)后继 x lowbit(x)6248440终止8880终止16四、查询前缀和知识点前缀和定义前缀和 sum(x) 表示原数组 a[1] a[2] … a[x] 的和。查询方法利用树状数组每个节点管理一个区间的特性将前缀和拆分为若干不重叠区间的和。查询步骤初始化结果 s 0。当 x 0 时将 c[x] 累加到 s 中。将 x 更新为它的前驱 x - lowbit(x)跳转到下一个区间。重复步骤 2 和 3直到 x 0。举例说明查询 sum(7) 的过程x 7c[7] 管理 [7, 7]累加 c[7]x 7 - 1 6。x 6c[6] 管理 [5, 6]累加 c[6]x 6 - 2 4。x 4c[4] 管理 [1, 4]累加 c[4]x 4 - 4 0结束。最终 sum(7) c[7] c[6] c[4]。示例代码// 查询前缀和求 [1, x] 的和。intsum(intx){ints0;for(;x0;x-lowbit(x)){sc[x];}returns;}五、点更新知识点点更新定义点更新 add(x, v) 表示将原数组位置 x 的值增加 v并同步更新树状数组中所有包含该位置的相关节点。更新方法修改位置 x 的值时只需要更新所有管辖区间包含 x 的节点。这些节点正好是 x 沿着后继方向不断向上跳所能到达的所有节点。更新步骤将 c[x] 增加 v。将 x 更新为它的后继 x lowbit(x)跳转到父节点。重复步骤 1 和 2直到 x n。举例说明更新 add(3, v) 的过程x 3更新 c[3]x 3 1 4。x 4更新 c[4]x 4 4 8。x 8更新 c[8]x 8 8 16若 16 n 则终止。共更新了 c[3]、c[4]、c[8]。示例代码// 单点增加位置 x 加 v。voidadd(intx,intv){for(;xn;xlowbit(x)){c[x]v;}}六、查询区间和知识点区间和定义区间和 range(l, r) 表示原数组中从位置 l 到位置 r 的所有元素之和即 a[l] a[l1] … a[r]。核心思路利用前缀和的差值来计算任意区间的和range(l, r) sum® - sum(l - 1)。其中 sum® 表示 [1, r] 的前缀和sum(l-1) 表示 [1, l-1] 的前缀和。查询步骤调用 sum® 求出前 r 个元素的和。调用 sum(l - 1) 求出前 l - 1 个元素的和。两者相减即为区间 [l, r] 的和。为什么正确sum® 包含了区间 [1, r] 的所有元素而 sum(l-1) 包含了区间 [1, l-1] 的所有元素。两者相减后剩下的正好是区间 [l, r] 中的元素和。举例说明查询 range(3, 6)先求 sum(6) c[6] c[4]覆盖区间 [5,6] 和 [1,4]。再求 sum(2) c[2]覆盖区间 [1,2]。range(3, 6) sum(6) - sum(2) (a[1]~a[6]) - (a[1]~a[2]) a[3] a[4] a[5] a[6]。时间复杂度区间和查询由两次前缀和查询相减得到每次前缀和查询为 O(log n)因此区间和查询的时间复杂度同样为 O(log n)。示例代码// 查询区间和[l, r]。intrange(intl,intr){returnsum(r)-sum(l-1);}七、树状数组代码实现知识点建树方式初始化时将原数组的每个元素 a[i] 通过 add(i, a[i]) 的方式依次加入树状数组。这种建树方式的时间复杂度为 O(n log n)。另一种建树方式可以先求出原数组的前缀和然后利用 c[i] sum[i] - sum[i - lowbit(i)] 直接计算出每个节点的值。这种建树方式的时间复杂度为 O(n)。lowbit 函数使用位运算 x -x 提取 x 最低位的 1是实现树状数组所有操作的基础。示例代码#includebits/stdc.husingnamespacestd;intc[1000005],n;// lowbit取x二进制最低位的1。intlowbit(intx){returnx-x;}// 点更新位置x加v。voidadd(intx,intv){for(;xn;xlowbit(x)){c[x]v;}}// 前缀和求[1, x]的和。intsum(intx){ints0;for(;x0;x-lowbit(x)){sc[x];}returns;}// 区间和[l, r]。intrange(intl,intr){returnsum(r)-sum(l-1);}intmain(){cinn;for(inti1;in;i){intx;cinx;add(i,x);}coutsum(5)endl;coutrange(2,4)endl;add(3,10);return0;}八、算法分析知识点时间复杂度单点更新每次循环 x 至少增加 lowbit(x)而 lowbit(x) 至少为 1因此每轮循环 x 的二进制最低位 1 至少左移一位。循环次数不超过 log₂n 次时间复杂度为 O(log n)。前缀和查询每次循环 x 至少减去 lowbit(x)x 的二进制中 1 的个数逐个减少。循环次数不超过 log₂n 次时间复杂度为 O(log n)。区间和查询由两次前缀和查询相减得到时间复杂度为 O(log n)。建树逐点插入建树的时间复杂度为 O(n log n)利用前缀和公式直接建树的时间复杂度为 O(n)。空间复杂度树状数组需要额外的辅助数组 c大小为 n 1空间复杂度为 O(n)。优缺点对比特性树状数组线段树时间复杂度O(log n)O(log n)空间复杂度O(n)O(4n)代码量极少约 10 行较多约 50 行以上支持的操作单点修改 前缀和区间修改 区间查询常数因子极小位运算 循环较大递归 多分支适用场景简单前缀和问题复杂区间操作问题适用场景树状数组适合用于求逆序对、区间和、差分数组维护等场景。当问题只需要单点修改和区间查询时树状数组是比线段树更优的选择。九、课程小结树状数组是一种用 O(log n) 时间维护前缀和的高效数据结构。lowbit(x) x -x用于提取 x 最低位的 1是树状数组的核心操作。查询前缀和时沿前驱方向x - lowbit(x)向下跳转累加节点值。单点更新时沿后继方向x lowbit(x)向上跳转更新所有父节点。区间和可以通过两个前缀和相减求得range(l, r) sum® - sum(l - 1)。树状数组常数小、代码短在单点修改前缀和场景中比线段树更有优势。