本课时有配套视频讲解，购买后即可观看（永久有效）
树状数组2
一、课上练习
编程练习
- 树状数组 2：L49937
二、知识总结
✨ 核心思想
在基础树状数组的基础上，我们利用差分数组的思想，将树状数组的能力扩展到：
- 区间修改 + 单点查询：维护差分数组的树状数组
- 区间修改 + 区间查询：维护两个树状数组，利用数学推导实现
这两种扩展使树状数组能够处理更广泛的问题。
✨ 算法原理
方案一：区间修改 + 单点查询
核心思路：对差分数组 d[i] = a[i] - a[i-1] 建树状数组。
- 区间修改 [l, r] 加 val：在差分数组上
d[l] += val，d[r+1] -= val - 单点查询 a[x]：就是差分数组的前缀和
a[x] = d[1] + d[2] + ... + d[x]
这样区间修改变成了两次单点修改，单点查询变成了前缀查询，都是 O(log n)。
方案二：区间修改 + 区间查询
需要查询前缀和 a[1] + a[2] + ... + a[x]。利用差分数组 d：
$$ \sum{i=1}^{x} a[i] = \sum{i=1}^{x} \sum_{j=1}^{i} d[j] $$
交换求和顺序：
$$ = \sum{j=1}^{x} d[j] \cdot (x - j + 1) = (x+1) \sum{j=1}^{x} d[j] - \sum_{j=1}^{x} d[j] \cdot j $$
因此，我们维护两个树状数组：
c1：维护d[i]的前缀和c2：维护d[i] * i的前缀和
前缀和公式：prefixSum(x) = (x + 1) * query(c1, x) - query(c2, x)
✨ 代码实现
区间修改 + 单点查询
树状数组 - 区间修改 + 单点查询
1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 500005;
5int c[MAXN]; // 差分数组的树状数组
6int a[MAXN]; // 原始数组
7int n, m;
8
9int lowbit(int x) { return x & (-x); }
10
11void update(int x, int val) {
12 for (; x <= n; x += lowbit(x))
13 c[x] += val;
14}
15
16// 前缀查询：返回差分前缀和 = a[x]的当前值
17int query(int x) {
18 int sum = 0;
19 for (; x > 0; x -= lowbit(x))
20 sum += c[x];
21 return sum;
22}
23
24// 区间[l, r]每个元素加val
25void rangeUpdate(int l, int r, int val) {
26 update(l, val);
27 update(r + 1, -val);
28}
29
30int main() {
31 ios::sync_with_stdio(false);
32 cin.tie(nullptr);
33
34 cin >> n >> m;
35 for (int i = 1; i <= n; i++) {
36 cin >> a[i];
37 }
38
39 // 用差分数组初始化树状数组
40 for (int i = 1; i <= n; i++) {
41 update(i, a[i] - a[i - 1]);
42 }
43
44 while (m--) {
45 int op;
46 cin >> op;
47 if (op == 1) {
48 int l, r, val;
49 cin >> l >> r >> val;
50 rangeUpdate(l, r, val); // 区间加
51 } else {
52 int x;
53 cin >> x;
54 cout << query(x) << "\n"; // 单点查询
55 }
56 }
57
58 return 0;
59}区间修改 + 区间查询
树状数组 - 区间修改 + 区间查询
1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 500005;
5typedef long long ll;
6
7ll c1[MAXN]; // 维护d[i]
8ll c2[MAXN]; // 维护d[i]*i
9int n, m;
10
11int lowbit(int x) { return x & (-x); }
12
13void update(ll* c, int x, ll val) {
14 for (; x <= n; x += lowbit(x))
15 c[x] += val;
16}
17
18ll query(ll* c, int x) {
19 ll sum = 0;
20 for (; x > 0; x -= lowbit(x))
21 sum += c[x];
22 return sum;
23}
24
25// 区间[l, r]每个元素加val
26void rangeUpdate(int l, int r, ll val) {
27 update(c1, l, val);
28 update(c1, r + 1, -val);
29 update(c2, l, val * l);
30 update(c2, r + 1, -val * (r + 1));
31}
32
33// 查询前缀和a[1]+...+a[x]
34ll prefixSum(int x) {
35 return (ll)(x + 1) * query(c1, x) - query(c2, x);
36}
37
38// 查询区间和a[l]+...+a[r]
39ll rangeQuery(int l, int r) {
40 return prefixSum(r) - prefixSum(l - 1);
41}
42
43int main() {
44 ios::sync_with_stdio(false);
45 cin.tie(nullptr);
46
47 cin >> n >> m;
48 for (int i = 1; i <= n; i++) {
49 ll x;
50 cin >> x;
51 rangeUpdate(i, i, x); // 用区间修改来初始化
52 }
53
54 while (m--) {
55 int op;
56 cin >> op;
57 if (op == 1) {
58 int l, r;
59 ll val;
60 cin >> l >> r >> val;
61 rangeUpdate(l, r, val);
62 } else {
63 int l, r;
64 cin >> l >> r;
65 cout << rangeQuery(l, r) << "\n";
66 }
67 }
68
69 return 0;
70}✨ 执行示例
以数组 a = [1, 3, 5, 2, 7]（n=5）为例，演示区间修改 + 区间查询。
初始状态：
| i | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| a[i] | 1 | 3 | 5 | 2 | 7 |
| d[i] | 1 | 2 | 2 | -3 | 5 |
操作 rangeUpdate(2, 4, 3) — 将 a[2]~a[4] 每个加 3：
差分数组变化：d[2] += 3，d[5] -= 3
| i | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| a[i]（修改后） | 1 | 6 | 8 | 5 | 7 |
| d[i]（修改后） | 1 | 5 | 2 | -3 | 2 |
查询 rangeQuery(1, 5)：
- prefixSum(5) = 6 × query(c1, 5) - query(c2, 5)
- query(c1, 5) = d[1]+d[2]+d[3]+d[4]+d[5] = 1+5+2+(-3)+2 = 7
- query(c2, 5) = 1×1+5×2+2×3+(-3)×4+2×5 = 1+10+6-12+10 = 15
- prefixSum(5) = 6 × 7 - 15 = 42 - 15 = 27
验证：1 + 6 + 8 + 5 + 7 = 27 ✓
✨ 解题步骤详解
- 分析操作类型：
- 单点修改 + 区间查询 → 基础树状数组
- 区间修改 + 单点查询 → 差分树状数组（一个 BIT）
- 区间修改 + 区间查询 → 双树状数组
- 推导公式：区间修改+区间查询的关键在于推导前缀和与差分数组的关系，将求和拆成两个独立的前缀和。
- 初始化：可以将初始值视为 n 次
rangeUpdate(i, i, a[i])操作。 - 注意边界：
update(r+1, ...)时确保r+1 <= n+1不会越界（通常数组多开几个位置）。
✨ 常见错误
- 忘记更新 c2：区间修改+区间查询需要同时更新两个树状数组。
- 公式推错：
prefixSum(x) = (x+1)*query(c1,x) - query(c2,x)，不要漏掉+1。 - 差分数组的还原方向搞反：
d[l] += val，d[r+1] -= val，不是反过来。 - 数据类型不一致：c2 中存的是
d[i]*i，数值可能很大，必须用long long。 - 数组大小不够：
update(r+1, ...)可能访问n+1，数组要多开。
✨ 算法评价
| 方案 | 修改复杂度 | 查询复杂度 | 额外空间 |
|---|---|---|---|
| 差分 BIT（区间改+单点查） | O(log n) | O(log n) | 1 个 BIT |
| 双 BIT（区间改+区间查） | O(log n) | O(log n) | 2 个 BIT |
与线段树对比：
- 树状数组代码量约为线段树的 1/3
- 常数小，运行速度快约 2-3 倍
- 但无法处理区间最值等非前缀运算
适用场景：区间加 + 区间求和、差分约束、需要高效区间操作但不需要最值查询的场合。
三、课后练习
编程练习
- 语文成绩：L49938