题解 P3368 【【模板】树状数组 2】
ZJYelizaveta
2017-10-14 22:03:34
### 描述
用树状数组来维护大小为序列 $n$，要求支持区间修改，单点查询。
$n \leq 500000, m \leq 500000$
### 分析
树状数组的本职是支持单点修改，区间查询的。这样把操作反过来以后应该怎样才能继续用树状数组来维护呢？
这里应用 `差分` 的思想。
比如原来树状数组的每一个叶子结点都是 $a[i]$，那么现在存放的就是 $c[i] = a[i] - a[i - 1]$。
$a[i] = c[i] + c[i - 1] + c[i - 2] + \cdots + c[2] +c[1]$，因此若要单点查询，那么直接查询前缀和即可。
至于区间修改很容易理解，就是 $modify[l, +k], modify[r + 1， -k]$，至于为什么自己在树状数组上画一下就可以了。
另，这里也提一下在要支持区间修改，区间查询的时候怎么办？
一样用树状数组来维护一个差分数组，区间修改同上。
$$\because a[i] = \sum_{j = 1}^{i}c[j] $$
$$\therefore \sum_{i = 1}^{n}a[i] = \sum_{i = 1}^{n}\sum_{j = 1}^{i}c[j] = \sum_{i = 1}^{n}(n - i + 1)c[i] = (n + 1)\sum_{i = 1}^{n}c[i] - \sum_{i = 1}^{n}c[i] \times i$$
开两个树状数组来维护这两项即可。
时间复杂度 $\Theta(nlogn)$
### 代码
```C++
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template<typename T> T readIn() {
T x(0), f(1);
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 500000 + 3;
const int MAX_M = 500000 + 3;
const int INF = 0x3f3f3f3f;
int n, m;
int a[MAX_N];
namespace fenwickTree {
int vec[MAX_N];
inline void init() {
memset(vec, 0, sizeof vec);
}
inline int lowbit(int x) {
return x & (-x);
}
inline void modify(int id, int x) {
while (id <= n) {
vec[id] += x;
id += lowbit(id);
}
}
inline int query(int id) {
int res = 0;
while (id >= 1) {
res += vec[id];
id -= lowbit(id);
}
return res;
}
}
using namespace fenwickTree;
int main()
{
n = readIn<int>(), m = readIn<int>();
for (int i = 1; i <= n; ++i) a[i] = readIn<int>();
init(); int last = 0;
for (int i = 1; i <= n; ++i) {
modify(i, a[i] - last);
last = a[i];
}
while (m--) {
int opt = readIn<int>();
if (opt == 1) {
int l = readIn<int>(), r = readIn<int>(), k = readIn<int>();
modify(l, k); modify(r + 1, -k);
}
else {
int pos = readIn<int>();
int ans = query(pos);
printf("%d\n", ans);
}
}
return 0;
}
```