企业官网建设流程全解析

教学目录

1. 树状数组定义
2. 区间长度
3. 前驱和后继
4. 查询前缀和
5. 点更新
6. 查询区间和
7. 树状数组代码实现
8. 算法分析
9. 课程小结

一、树状数组定义

知识点

• 树状数组的引入
  给定一个长度为 n 的数组 a，需要支持两种操作：
  1. 将第 x 个元素的值增加 v。
  2. 查询区间 [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 的前驱为 x - lowbit(x)。
  前驱节点对应的是查询前缀和时，当前节点管辖区间之前紧邻的区间的起点。
• 后继节点
  在树状数组中，节点 x 的后继为 x + lowbit(x)。
  后继节点对应的是单点更新时，需要向上更新所有覆盖了位置 x 的父节点。
• 前驱的作用
  查询前缀和 sum(x) 时，每次迭代都将当前节点 x 更新为其前驱 x - lowbit(x)。
  这样可以快速跳过已累加的区间，跳转到下一个需要累加的区间。
• 后继的作用
  单点更新 add(x, v) 时，每次迭代都将当前节点 x 更新为其后继 x + lowbit(x)。
  这样可以自底向上更新所有包含位置 x 的节点。

示例：x = 6 的前驱和后继

四、查询前缀和

知识点

• 前缀和定义
  前缀和 sum(x) 表示原数组 a[1] + a[2] + … + a[x] 的和。
• 查询方法
  利用树状数组每个节点管理一个区间的特性，将前缀和拆分为若干不重叠区间的和。
• 查询步骤
  1. 初始化结果 s = 0。
  2. 当 x > 0 时，将 c[x] 累加到 s 中。
  3. 将 x 更新为它的前驱 x - lowbit(x)，跳转到下一个区间。
  4. 重复步骤 2 和 3，直到 x = 0。
• 举例说明
  查询 sum(7) 的过程：
  x = 7，c[7] 管理 [7, 7]，累加 c[7]，x = 7 - 1 = 6。
  x = 6，c[6] 管理 [5, 6]，累加 c[6]，x = 6 - 2 = 4。
  x = 4，c[4] 管理 [1, 4]，累加 c[4]，x = 4 - 4 = 0，结束。
  最终 sum(7) = c[7] + c[6] + c[4]。

示例代码

// 查询前缀和：求 [1, x] 的和。intsum(intx){ints=0;for(;x>0;x-=lowbit(x)){s+=c[x];}returns;}

五、点更新

知识点

• 点更新定义
  点更新 add(x, v) 表示将原数组位置 x 的值增加 v，并同步更新树状数组中所有包含该位置的相关节点。
• 更新方法
  修改位置 x 的值时，只需要更新所有管辖区间包含 x 的节点。
  这些节点正好是 x 沿着后继方向不断向上跳所能到达的所有节点。
• 更新步骤
  1. 将 c[x] 增加 v。
  2. 将 x 更新为它的后继 x + lowbit(x)，跳转到父节点。
  3. 重复步骤 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(;x<=n;x+=lowbit(x)){c[x]+=v;}}

六、查询区间和

知识点

• 区间和定义
  区间和 range(l, r) 表示原数组中从位置 l 到位置 r 的所有元素之和，即 a[l] + a[l+1] + … + a[r]。
• 核心思路
  利用前缀和的差值来计算任意区间的和：
  range(l, r) = sum® - sum(l - 1)。
  其中 sum® 表示 [1, r] 的前缀和，sum(l-1) 表示 [1, l-1] 的前缀和。
• 查询步骤
  1. 调用 sum® 求出前 r 个元素的和。
  2. 调用 sum(l - 1) 求出前 l - 1 个元素的和。
  3. 两者相减即为区间 [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，是实现树状数组所有操作的基础。

示例代码

#include<bits/stdc++.h>usingnamespacestd;intc[1000005],n;// lowbit：取x二进制最低位的1。intlowbit(intx){returnx&-x;}// 点更新：位置x加v。voidadd(intx,intv){for(;x<=n;x+=lowbit(x)){c[x]+=v;}}// 前缀和：求[1, x]的和。intsum(intx){ints=0;for(;x>0;x-=lowbit(x)){s+=c[x];}returns;}// 区间和：[l, r]。intrange(intl,intr){returnsum(r)-sum(l-1);}intmain(){cin>>n;for(inti=1;i<=n;i++){intx;cin>>x;add(i,x);}cout<<sum(5)<<endl;cout<<range(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)。

• 优缺点对比

• 适用场景
  树状数组适合用于求逆序对、区间和、差分数组维护等场景。
  当问题只需要单点修改和区间查询时，树状数组是比线段树更优的选择。

九、课程小结

1. 树状数组是一种用 O(log n) 时间维护前缀和的高效数据结构。
2. lowbit(x) = x & -x，用于提取 x 最低位的 1，是树状数组的核心操作。
3. 查询前缀和时，沿前驱方向（x - lowbit(x)）向下跳转，累加节点值。
4. 单点更新时，沿后继方向（x + lowbit(x)）向上跳转，更新所有父节点。
5. 区间和可以通过两个前缀和相减求得：range(l, r) = sum® - sum(l - 1)。
6. 树状数组常数小、代码短，在单点修改前缀和场景中比线段树更有优势。