给出一个C++树状数组的模板
时间: 2023-07-13 14:12:47 浏览: 47
以下是一个基本的 C++ 树状数组的模板:
```c++
const int MAXN = 100005;
int n;
int c[MAXN];
int lowbit(int x) {
return x & -x;
}
void update(int x, int v) {
while (x <= n) {
c[x] += v;
x += lowbit(x);
}
}
int query(int x) {
int res = 0;
while (x) {
res += c[x];
x -= lowbit(x);
}
return res;
}
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
int x;
cin >> x;
update(i, x);
}
int q;
cin >> q;
while (q--) {
int l, r;
cin >> l >> r;
cout << query(r) - query(l - 1) << endl;
}
return 0;
}
```
其中 `lowbit(x)` 函数返回 `x` 的二进制表示下最低的非零位所对应的数值,即 `lowbit(x) = x & -x`。树状数组的 `update(x, v)` 函数将第 `x` 个元素的值增加 `v`,而 `query(x)` 函数返回前 `x` 个元素的和。在 `main` 函数中,我们先读入数组中的元素并依次调用 `update` 函数进行初始化,然后读入查询次数 `q`,每次查询时调用 `query` 函数计算答案并输出即可。