一、课程基本信息
课程主题： 树状数组（Binary Indexed Tree / Fenwick Tree）
适用对象： 已掌握数组、前缀和、差分、基础循环、函数封装，了解简单时间复杂度分析的学生。
课程定位： 树状数组是竞赛算法和工程数据处理中的基础数据结构，主要用于解决“动态前缀和”“动态区间和”“频次数组统计”“逆序对”“区间加与区间求和”等问题。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二、课程目标
1. 知识目标
学生应理解：
1. 为什么普通前缀和不能高效支持修改。
2. 树状数组解决的是哪一类问题。
3. lowbit(x) 的含义与作用。
4. 树状数组中 tree[i] 保存的区间含义。
5. 单点修改、前缀查询、区间查询的基本操作。
6. 树状数组和前缀和、差分、线段树之间的关系。
2. 能力目标
学生应能够：
1. 独立写出树状数组的基础模板。
2. 用树状数组完成“单点修改 + 区间求和”。
3. 用树状数组完成“区间修改 + 单点查询”。
4. 用两个树状数组完成“区间修改 + 区间查询”。
5. 用树状数组统计逆序对。
6. 结合离散化处理数值范围较大的问题。
7. 判断一道题是否适合使用树状数组。
3. 思维目标
学生应形成以下意识：
1. 树状数组本质上不是一棵真正显式建出来的树，而是用二进制规律组织数组。
2. 树状数组适合解决“可拆成前缀信息”的动态问题。
3. 树状数组的核心思想是：用若干个长度为 2 的幂次的区间，快速拼出前缀和。
4. 不要只背模板，要能解释每一步为什么这样跳。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三、先修知识回顾
1. 普通数组求区间和
给定数组：
如果直接求区间 [l, r] 的和，需要从 l 加到 r，时间复杂度为：
最坏情况下是：
如果查询很多次，就会很慢。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 前缀和
定义：
那么区间和可以快速得到：
查询复杂度：
但是如果数组中某个值发生修改，例如：
那么所有 S[pos]、S[pos + 1]、...、S[n] 都要变化，修改复杂度为：
所以普通前缀和适合“静态数组”，不适合“频繁修改”。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 问题引入
我们希望支持两种操作：
如果用普通数组：
如果用前缀和：
有没有一种结构可以让修改和查询都比较快？
树状数组可以做到：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
四、树状数组的核心思想
1. 树状数组解决什么问题
树状数组主要解决一类问题：
> 一个数组需要不断修改，同时又需要快速查询前缀和或区间和。
基础版本支持：
通过差分和双树状数组，还可以支持：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 树状数组不是普通前缀和
普通前缀和 S[i] 保存的是：
树状数组 tree[i] 保存的是：
也就是说，tree[i] 保存的是一个以 i 结尾、长度为 lowbit(i) 的小区间。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
五、LOWBIT 详解
1. LOWBIT 是什么
lowbit(x) 表示整数 x 的二进制表示中，最低位的 1 所代表的数值。
公式：
例如：
x 二进制 lowbit(x) 含义 1 0001 1 最低位的 1 是 1 2 0010 2 最低位的 1 是 2 3 0011 1 最低位的 1 是 1 4 0100 4 最低位的 1 是 4 5 0101 1 最低位的 1 是 1 6 0110 2 最低位的 1 是 2 7 0111 1 最低位的 1 是 1 8 1000 8 最低位的 1 是 8
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 为什么 X & -X 可以得到 LOWBIT
在计算机中，负数通常用补码表示。
例如：
然后：
所以：
直观理解：
> x & -x 会保留 x 二进制中最靠右的那个 1，并把其他位都变成 0。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. LOWBIT 在树状数组中的作用
lowbit(i) 决定了 tree[i] 管辖的区间长度。
例如：
i lowbit(i) tree[i] 保存的区间 1 1 [1, 1] 2 2 [1, 2] 3 1 [3, 3] 4 4 [1, 4] 5 1 [5, 5] 6 2 [5, 6] 7 1 [7, 7] 8 8 [1, 8] 9 1 [9, 9] 10 2 [9, 10] 12 4 [9, 12] 16 16 [1, 16]
规律：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
六、树状数组的结构理解
假设原数组下标从 1 开始：
树状数组各位置表示：
可以看出：
* 有些位置只管自己。
* 有些位置管两个数。
* 有些位置管四个数。
* 有些位置管八个数。
这些区间长度正好是 lowbit(i)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
七、前缀和查询操作
1. 目标
查询：
即：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 查询思想
树状数组用若干个不重叠的小区间拼出 [1, x]。
例如查询 sum(7)：
树状数组拆成：
所以：
下标变化：
每次执行：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 查询代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. 查询过程示例
假设查询 sum(13)。
二进制：
查询路径：
对应区间：
合并后正好是：
所以：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
八、单点修改操作
1. 目标
执行：
也就是把位置 pos 上的值增加 delta。
由于 tree[i] 保存的是某个区间的和，所以凡是包含 pos 的 tree[i] 都需要更新。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 修改思想
例如修改 a[3] += delta。
哪些 tree[i] 包含 a[3]？
所以需要更新：
下标变化：
每次执行：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 修改代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. 修改过程示例
假设 n = 16，执行：
修改路径：
说明：
因此都要加上 delta。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
九、区间查询
1. 基本公式
查询区间 [l, r] 的和：
树状数组中写成：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 为什么可以这样做
prefixSum(r) 表示：
prefixSum(l - 1) 表示：
两者相减，剩下：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十、基础模板
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十一、建树方法
方法一：逐个 ADD 建树
复杂度：
优点：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
方法二：线性建树
因为：
可以先：
再把当前节点的信息传给父节点：
完整代码：
复杂度：
适合：
课堂建议：
初学者先掌握 add 建树，线性建树作为提高内容。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十二、树状数组的典型用途一：单点修改 + 区间查询
1. 问题描述
有一个数组，支持两种操作：
这是树状数组最基础的用途。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 解题思路
* 修改一个点：使用 add(pos, delta)。
* 查询区间：使用 sum(r) - sum(l - 1)。
复杂度：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 适用场景
例如：
1. 动态维护商品库存总量。
2. 动态维护游戏中若干玩家积分区间和。
3. 在线统计某一段时间内的访问量。
4. 动态维护一段序列的权值和。
5. 竞赛题中的区间求和模板题。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十三、树状数组的典型用途二：频次数组统计
1. 问题背景
有时我们不直接维护原数组，而是维护一个“频次数组”。
例如，数字出现次数：
树状数组可以维护 cnt，快速回答：
即：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 插入一个数字
如果插入数字 x：
表示：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 查询小于等于 X 的个数
表示：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. 查询小于 X 的个数
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
5. 查询大于 X 的个数
如果当前已经插入 total 个数，那么：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
6. 适用场景
1. 统计逆序对。
2. 动态统计排名。
3. 动态维护每个分数段的人数。
4. 查询当前比某个数小或大的数有多少个。
5. 解决“左边有多少个数小于当前值”“右边有多少个数大于当前值”等问题。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十四、树状数组的典型用途三：统计逆序对
1. 逆序对定义
给定数组 a，如果满足：
那么 (i, j) 是一个逆序对。
例如：
逆序对有：
所以逆序对数量为 2。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 朴素做法
双重循环：
复杂度：
当 n 很大时会超时。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 树状数组思路
从左到右扫描数组。
当处理 a[i] 时，前面已经出现过 i - 1 个数。
我们想知道：
如果树状数组维护的是出现次数，则：
然后把当前数加入：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. 为什么要离散化
如果 a[i] 很大，例如：
不能直接开一个大小为 10^9 的树状数组。
这时需要离散化。
离散化的作用：
> 保留大小关系，把原来的大数映射成较小的排名。
例如：
大小关系没有变，但值域变小了。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
5. C++ 代码：逆序对
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
6. 逆序对用途
1. 衡量一个序列的混乱程度。
2. 判断排序需要交换的次数。
3. 数据排序稳定性分析。
4. 竞赛中常用于排列、排名、交换次数等问题。
5. 某些推荐系统、排名比较中可以用来衡量两个排序的差异。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十五、树状数组的典型用途四：区间修改 + 单点查询
1. 问题描述
支持两种操作：
如果直接对 [l, r] 每个位置修改，复杂度是 O(n)。
树状数组可以借助差分做到：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 差分数组回顾
定义差分数组：
则：
也就是说：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 区间加如何转化为差分修改
如果要给 [l, r] 整体加 delta：
在差分数组中只需要：
原因：
* 从 l 开始，前缀和多了 delta。
* 从 r + 1 开始，把这个影响抵消掉。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. 树状数组维护差分
如果树状数组维护的是 d，那么：
也就是：
区间修改：
单点查询：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
5. C++ 模板
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
6. 适用场景
1. 一段时间内给所有用户增加积分，然后查询某个用户积分。
2. 区间批量调整库存，查询某个商品当前库存。
3. 游戏中给某一段编号的角色统一加属性，查询单个角色属性。
4. 维护区间标记、区间增量、某点状态。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十六、树状数组的典型用途五：区间修改 + 区间查询
1. 问题描述
支持两种操作：
这比“区间修改 + 单点查询”更难。
需要使用两个树状数组。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 推导思路
仍然使用差分数组 d：
我们要求前缀和：
展开：
观察每个 d[i] 出现了多少次：
所以：
因此，只要维护两个东西：
前缀和为：
区间和：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 区间加的更新方式
区间 [l, r] 加 delta，差分变化为：
因此：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. C++ 模板
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
5. 初始化原数组
如果原数组一开始不是全 0，可以对每个位置执行：
或者先构造差分数组再加入。
初学阶段建议使用：
虽然是 O(n log n)，但清晰可靠。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
6. 适用场景
1. 多次区间加工资，查询某段员工工资总和。
2. 多次区间增加访问量，查询某个时间段总访问量。
3. 批量调整成绩或权值，查询区间总分。
4. 区间累计贡献问题。
5. 线段树懒标记能做的部分区间加、区间和问题，树状数组也能做。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十七、树状数组的典型用途六：查询第 K 小 / 第 K 个位置
1. 问题描述
假设树状数组维护的是频次数组 cnt。
现在要查询：
或者：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 朴素做法
可以二分答案：
每次 sum(pos) 是 O(log n)，二分也是 O(log n)，所以总复杂度：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 树状数组倍增查找
可以利用树状数组结构，用类似二进制跳跃的方法做到：
核心思想：
从高位到低位尝试往右跳，如果跳过去之后前缀和仍然小于 k，说明答案还在更右边。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. C++ 代码
如果 n <= 100000，1 << 20 足够。
更稳妥的写法：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
5. 适用场景
1. 动态排名系统。
2. 动态中位数。
3. 多重集合中查询第 k 小。
4. 根据频率找第 k 个元素。
5. 抽奖、权重选择、订单排位等问题。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十八、树状数组的典型用途七：二维树状数组
1. 问题描述
一维树状数组维护的是数组。
二维树状数组维护的是矩阵。
支持：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 二维前缀和回顾
矩形 [x1, y1] 到 [x2, y2] 的和：
二维树状数组也遵循这个容斥公式。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 单点修改
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. 查询左上角矩形和
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
5. 查询任意矩形和
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
6. 复杂度
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
7. 适用场景
1. 动态矩阵求和。
2. 棋盘区域统计。
3. 图像像素区域统计。
4. 地图网格热度统计。
5. 二维坐标点权值维护。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十九、树状数组的典型用途八：离线查询
1. 什么是离线查询
在线查询：
离线查询：
树状数组常和离线排序结合。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 常见问题类型
例如：
可以将询问按横坐标排序，将点逐渐加入树状数组，用树状数组维护纵坐标出现次数。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 适用场景
1. 区间内大于某值的数有多少个。
2. 二维偏序问题。
3. 静态数组多次条件查询。
4. 扫描线问题。
5. 按时间、坐标、权值排序后逐步加入数据。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二十、树状数组和线段树的比较
对比项 树状数组 线段树 代码长度 短 较长 理解难度 中等 较高 常数 小 较大 空间 O(n) 通常 O(4n) 单点修改 + 区间和 支持 支持 区间加 + 区间和 双树状数组支持 懒标记支持 区间最值 不适合普通动态最值 适合 复杂区间操作 不适合 更适合 第 k 小 可支持频次数组 也可支持 二维扩展 可支持但空间可能大 可支持但复杂
结论
树状数组适合：
线段树适合：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二十一、树状数组能做和不能做的事情
1. 非常适合做的事情
1. 单点加，区间求和。
2. 区间加，单点查询。
3. 区间加，区间求和。
4. 频次数组维护。
5. 逆序对统计。
6. 动态排名。
7. 查找第 k 小。
8. 离散化后处理大值域数据。
9. 二维矩阵单点修改和矩形查询。
10. 一些离线扫描线问题。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 不太适合做的事情
1. 区间最大值和最小值的复杂动态维护。
2. 区间赋值后再求和。
3. 同时有区间乘法、区间加法、区间求和的复杂问题。
4. 需要维护复杂结构信息的问题。
5. 无法转化为前缀信息的问题。
