#P3368. 【模板】树状数组 2

### 关于树状数组2的模板与实现 树状数组2通常指的是支持 **区间修改** 和 **单点查询** 或者 **区间查询** 的高级版本。相比于基础版树状数组（仅支持单点修改和区间查询），它通过维护两个独立的树状数组来完成更复杂的操作。 #### 基本原理 为了处理区间加法问题，可以引入差分的思想[^3]。具体来说，定义 `ans` 表示实际的前缀和，`ans1` 是第一个树状数组存储的前缀和，`ans2` 是第二个树状数组用于修正偏移量，则有如下关系： \[ \text{ans}[i] = \text{ans1}[i] \times i - \text{ans2}[i]. \] 这种设计使得我们可以高效地执行以下两种操作： 1. 对某个区间的值加上一个常数。 2. 查询某个位置的实际数值或者某一区间的总和。 以下是具体的代码实现： ```cpp #include <bits/stdc++.h> using namespace std; // 定义最大数据范围 const int MAXN = 1e5 + 5; long long c1[MAXN], c2[MAXN]; // 两个树状数组分别记录原始值和偏移量 // lowbit函数计算二进制最低位1对应的十进制值 inline int lowbit(int x) { return x & (-x); } // 更新树状数组c1和c2的操作 void update(long long* tree, int pos, int delta, int n) { while (pos <= n) { tree[pos] += delta; pos += lowbit(pos); } } // 获取树状数组c1或c2的前缀和 long long query(long long* tree, int pos) { long long res = 0; while (pos > 0) { res += tree[pos]; pos -= lowbit(pos); } return res; } // 区间[a,b]增加val void add_range(int a, int b, int val, int n) { update(c1, a, val, n); // 修改a处的影响 update(c1, b + 1, -val, n); // 取消b+1之后的影响 update(c2, a, val * (a - 1), n); // 修改a处的偏移影响 update(c2, b + 1, -val * b, n); // 取消b+1之后的偏移影响 } // 单点查询第k个元素的真实值 long long get_value(int k) { return query(c1, k) * k - query(c2, k); } int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; // 数组长度n，m次操作 memset(c1, 0, sizeof(c1)); memset(c2, 0, sizeof(c2)); for (int i = 1; i <= n; ++i) { // 初始化数组 int temp; cin >> temp; add_range(i, i, temp, n); // 将初始值转化为区间更新的形式 } for (int i = 0; i < m; ++i) { char op; cin >> op; if (op == 'Q') { // 查询操作 int idx; cin >> idx; cout << get_value(idx) << "\n"; } else if (op == 'C') { // 修改操作 int l, r, v; cin >> l >> r >> v; add_range(l, r, v, n); } } return 0; } ``` 上述代码实现了树状数组2的核心功能——即支持区间修改和单点查询的功能。其中的关键在于利用了两个树状数组 `c1` 和 `c2` 来模拟差分数组的效果。 --- ### 性能分析 相比线段树，树状数组2具有更高的效率和更低的空间开销，在许多场景下更适合快速解决问题[^2]。然而需要注意的是，当题目需求更加复杂时（如多维查询、动态开点等），可能仍需借助线段树或其他高级结构。 ---