好的，我已经记住了已经讲解过的题目列表。现在，我为你随机选择并详细讲解一个尚未讲过的算法与数据结构专题知识点。
二叉索引树（Fenwick Tree / Binary Indexed Tree）的区间修改与区间查询详解
1. 知识点/题目描述
我们之前已经学习了二叉索引树（Fenwick Tree） 的基本原理与实现，它可以在 O(log n) 时间内高效地进行单点修改和前缀和查询。这已经能够解决“动态前缀和”这一类问题。
但在许多实际场景中，我们不仅需要频繁修改单个元素，更需要对一个连续的区间进行统一修改（例如，给数组 arr[l...r] 的每个元素都加上一个值 delta），同时还需要高效地查询区间和（即 arr[l] + arr[l+1] + ... + arr[r]）。
今天要深入讲解的，就是如何利用两个 Fenwick Tree 来组合实现 O(log n) 复杂度的区间修改和区间查询。这是 Fenwick Tree 的一个经典高级应用。
2. 问题建模与思路启发
假设我们有一个初始全为 0 的数组 A[1...n]。
我们需要支持两种操作：
- 区间修改：
Add(l, r, delta)-> 对A[l]到A[r]的每一个元素都加上delta。 - 区间查询：
Query(l, r)-> 返回A[l] + ... + A[r]的和。
朴素思考的困境：
- 如果直接修改数组，区间修改是 O(n)，区间查询也是 O(n)。
- 如果用基本的 Fenwick Tree（单点修改，前缀查询），要实现区间修改
Add(l, r, delta)，需要对l到r每个点执行update(i, delta)，这又是 O(n log n)。
我们需要一种方法，能将“区间修改”这个批量操作，转换成对 Fenwick Tree 的 O(log n) 次单点修改。
关键思路：差分数组的威力
还记得差分数组（Difference Array） 吗？对于原数组 A，我们定义其差分数组 D，其中：
D[1] = A[1]D[i] = A[i] - A[i-1], for i > 1
差分数组有一个美妙的性质：
- 对
A的区间[l, r]加上delta，等价于在差分数组D上进行两次单点修改：D[l] += delta,D[r+1] -= delta。 A的前缀和PrefixSum[k] = A[1]+...+A[k]， 可以通过D来计算：PrefixSum[k] = D[1] + 2*D[2] + 3*D[3] + ... + k*D[k]。
这个性质给了我们启发：如果我们用 Fenwick Tree 来维护差分数组 D，那么：
- 区间修改 (
Add(l, r, delta)) -> 转换为对D的两个单点修改 -> 调用两次tree.update(l, delta)和tree.update(r+1, -delta)。复杂度 O(log n)。 - 但查询
A的前缀和 (PrefixSum(k))，公式是sum_{i=1}^{k} (i * D[i])。这不再是简单的D的前缀和，而是带有系数i的加权和。一个只维护D[i]的 Fenwick Tree 无法直接得出这个结果。
3. 解决方案：双树模型
为了高效计算 sum_{i=1}^{k} (i * D[i])，我们需要维护两个序列：
D[i]本身。i * D[i]。
我们可以使用两个 Fenwick Tree，分别来维护这两个序列的前缀和。
- 我们称它们为
BIT1和BIT2。 - 初始化： 数组
A初始全 0，所以D也全 0，两个树都初始化为 0。
操作定义：
-
区间修改
Add(l, r, delta):- 在
BIT1上，执行update(l, delta)和update(r+1, -delta)。这维护了D[i]的差分性质。 - 在
BIT2上，执行update(l, delta * l)和update(r+1, -delta * (r+1))。这维护了i * D[i]对应的差分性质。 - 这一步完美对应了差分数组的更新规则。
- 在
-
前缀和查询
PrefixSum(k):- 我们希望计算
S = A[1] + ... + A[k] = sum_{i=1}^{k} ( (k+1-i) * D[i] )?。让我们严谨推导一下。 - 根据差分定义
A[i] = sum_{j=1}^{i} D[j]。 - 所以
PrefixSum(k) = sum_{i=1}^{k} A[i] = sum_{i=1}^{k} sum_{j=1}^{i} D[j]。 - 改变求和顺序：
= sum_{j=1}^{k} D[j] * (k - j + 1)。 - 展开：
= (k+1) * sum_{j=1}^{k} D[j] - sum_{j=1}^{k} (j * D[j])。 - 看！
sum_{j=1}^{k} D[j]正是BIT1的前缀和查询query1(k)。 sum_{j=1}^{k} (j * D[j])正是BIT2的前缀和查询query2(k)。
- 我们希望计算
因此，核心公式诞生：
PrefixSum(k) = (k+1) * query1(k) - query2(k)
- 区间和查询
Query(l, r):- 这很容易通过两个前缀和相减得到：
Query(l, r) = PrefixSum(r) - PrefixSum(l-1)。
- 这很容易通过两个前缀和相减得到：
4. 算法步骤总结
数据结构：
- 两个大小均为
n+2的 Fenwick Tree 数组，bit1和bit2（下标从 1 开始）。
核心操作：
-
add(l, r, delta)- 区间加:_update(bit1, l, delta)_update(bit1, r+1, -delta)_update(bit2, l, delta * l)_update(bit2, r+1, -delta * (r+1))
（_update是标准的 Fenwick Tree 单点更新函数）
-
prefix_sum(k)- 前缀和:sum1 = _query(bit1, k)// 查询 bit1 到 k 的前缀和sum2 = _query(bit2, k)// 查询 bit2 到 k 的前缀和return (k+1) * sum1 - sum2
（_query是标准的 Fenwick Tree 前缀查询函数）
-
range_sum(l, r)- 区间和:return prefix_sum(r) - prefix_sum(l-1)
5. 复杂度分析与示例
- 时间复杂度： 所有操作（区间修改、区间查询）都只涉及常数次（2或4次）Fenwick Tree 的基本操作，因此时间复杂度均为 O(log n)。
- 空间复杂度： O(n)，用于存储两个树。
示例验证：
初始： A = [0, 0, 0, 0, 0] (n=5)
add(2, 4, 5)-> 给 A[2], A[3], A[4] 加 5。- bit1: update(2,5), update(5, -5)
- bit2: update(2,52=10), update(5, -55=-25)
add(1, 3, 2)-> 给 A[1], A[2], A[3] 加 2。- bit1: update(1,2), update(4, -2)
- bit2: update(1,21=2), update(4, -24=-8)
range_sum(2, 4)= ?prefix_sum(4)= (4+1)*_query(bit1,4) - _query(bit2,4)- 计算 bit1 到 4 的和: D[1]=2, D[2]=5, D[3]=0, D[4]=-2 => sum1 = 2+5+0-2 = 5
- 计算 bit2 到 4 的和: 1D[1]=2, 2D[2]=10, 3D[3]=0, 4D[4]=-8 => sum2 = 2+10+0-8 = 4
prefix_sum(4)= 5*5 - 4 = 21
prefix_sum(1)= (1+1)_query(bit1,1) - _query(bit2,1) = 22 - 2 = 2range_sum(2,4)= 21 - 2 = 19
手动验证 A 数组：
经过操作后，A = [2, (0+5+2)=7, (0+5+2)=7, (0+5)=5, 0]
A[2]+A[3]+A[4] = 7+7+5 = 19。结果正确。
6. 核心要点与总结
- 这个技巧的精髓在于利用差分思想，将区间修改转化为两次单点修改。
- 为了支持快速求取原数组的前缀和，需要同时维护差分数组
D[i]和其加权形式i*D[i]的前缀和，因此引入了双 Fenwick Tree 模型。 - 所有操作的复杂度均为 O(log n)，在解决“区间修改、区间求和”这类问题上，其代码量比线段树（Segment Tree with Lazy Propagation）更简洁，常数更小，是竞赛和面试中的利器。
- 请注意，此方法支持的是区间加法和区间求和。如果需要区间赋值、求最大值等更复杂的操作，线段树依然是更灵活的选择。