题解：P3368 【模板】树状数组 2
mazhenhao0235
·
·
题解
P3368 题解：树状数组2
题目传送门
题目描述
给定一个长度为 n 的数组 f ，以及 m 次操作。操作分为两种：
- 区间修改：将数组 f 中下标在 [x, y] 范围内的元素都加上 z 。
- 单点查询：查询数组 f 中下标为 x 的元素的值。
解题思路
这道题可以使用树状数组来高效地处理区间修改和单点查询。树状数组是一种支持单点修改和区间查询的数据结构，但通过差分的思想，我们可以将其扩展为支持区间修改和单点查询。
代码解析
树状数组的定义：
$lowbit(x)$ ：返回 $ x $ 的二进制表示中最低位的 $ 1 $ 所对应的值。
$add(x, k)$ ：在树状数组的第 $ x $ 个位置加上 $ k $ ，并更新其父节点。
$search(x)$ ：查询树状数组中前 $ x $ 个元素的和。
### 初始化：
读取数组 $ f $ 的初始值。
### 处理操作：
区间修改：对于操作 $ 1 $ $ x $ $ y $ $ z $ ，我们通过差分的思想，在 $ x $ 位置加上 $ z $，在 $ y+1 $ 位置减去 $ z $ 。这样，查询时就可以通过前缀和得到每个位置的实际值。
单点查询：对于操作 $ 2 $ $ x $，我们查询树状数组中前 $ x $ 个元素的和，并加上 $ f[x] $ 的初始值，得到最终的结果。
## 代码
```cpp
#include <bits/stdc++.h> //万能头
using namespace std;
const int N = 500005;
int n, m;
int f[N], fa[N];
// 返回 x 的二进制表示中最低位的 1 所对应的值
int lowbit(int x) {
return x & -x;
}
// 在树状数组的第 x 个位置加上 k
void add(int x, int k) {
while (x <= n) {
fa[x] += k;
x += lowbit(x);
}
}
// 查询树状数组中前 x 个元素的和
int search(int x) {
int ans = 0;
while (x != 0) {
ans += fa[x];
x -= lowbit(x);
}
return ans;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> f[i];
for (int i = 1, op, x, y, z; i <= m; i++) {
cin >> op;
if (op == 1) {
// 区间修改
cin >> x >> y >> z;
add(x, z);
add(y + 1, -z);
} else {
// 单点查询
cin >> x;
cout << f[x] + search(x) << "\n";
}
}
}
```
## 复杂度分析：
时间复杂度：
每次区间修改和单点查询的时间复杂度均为 $ O(log n) $ 。
总的时间复杂度为 $ O(m log n) $。
空间复杂度：树状数组 $ fa $ 的空间复杂度为 $ O(n) $ 。
## 总结：
通过使用树状数组和差分的思想，我们可以高效地处理区间修改和单点查询操作。这种方法在时间复杂度和空间复杂度上都表现良好，适用于处理大规模数据的场景。