codeforces 树状数组

树状数组（Fenwick Tree）是一种用于高效处理区间和查询的数据结构，常用于解一维数组的前缀和、区间更新和查询等问题。

在 Codeforces 上，树状数组常被用来解决一些与区间和查询有关的问题。它可以在 O(logn) 的时间内完成单点更新和查询，以及区间求和等操作。

下面是一个简单的示例代码，展示了如何实现一个基本的树状数组：

#include <iostream>
#include <vector>
using namespace std;

// 获取最低位的 1
int getLowbit(int x) {
    return x & -x;
}

// 树状数组的单点更新操作
void update(vector<int>& fenwick, int index, int delta) {
    while (index < fenwick.size()) {
        fenwick[index] += delta;
        index += getLowbit(index);
    }
}

// 树状数组的前缀和查询操作
int query(vector<int>& fenwick, int index) {
    int sum = 0;
    while (index > 0) {
        sum += fenwick[index];
        index -= getLowbit(index);
    }
    return sum;
}

int main() {
    int n;
    cin >> n;

    vector<int> fenwick(n + 1, 0);

    // 初始化树状数组
    for (int i = 1; i <= n; i++) {
        int val;
        cin >> val;
        update(fenwick, i, val);
    }

    // 进行查询操作
    int q;
    cin >> q;
    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int index, delta;
            cin >> index >> delta;
            update(fenwick, index, delta);
        } else if (type == 2) {
            int l, r;
            cin >> l >> r;
            int sum = query(fenwick, r) - query(fenwick, l - 1);
            cout << sum << endl;
        }
    }

    return 0;
}

在这个示例中，我们使用了一个长度为 n 的数组 `fenwick` 来表示树状数组。`update` 函数用于更新树状数组中的某个元素，`query` 函数用于查询树状数组中某个区间的和。

你可以根据具体问题的要求进行相应的修改和扩展。希望对你有所帮助！如果有任何疑问，请随时提问。