C++树状数组的编程实践案例

树状数组（Binary Indexed Tree）是一种用来高效地处理动态区间和的数据结构。下面是一个C++的树状数组的实现案例：

#include <iostream>#include <vector>using namespace std;class FenwickTree {private:    vector<int> tree;public:    FenwickTree(int n) {        tree.assign(n + 1, 0);    }    void update(int idx, int val) {        while (idx < tree.size()) {            tree[idx] += val;            idx += idx & (-idx);        }    }    int query(int idx) {        int sum = 0;        while (idx > 0) {            sum += tree[idx];            idx -= idx & (-idx);        }        return sum;    }};int main() {    vector<int> nums = {1, 3, 5, 7, 9, 11};    FenwickTree ft(nums.size());    // 构建树状数组    for (int i = 0; i < nums.size(); i++) {        ft.update(i + 1, nums[i]);    }    // 查询区间和    cout << "Sum of first 3 elements: " << ft.query(3) << endl; // 输出: 9    cout << "Sum of elements from index 2 to 5: " << ft.query(5) - ft.query(1) << endl; // 输出: 32    return 0;}

在这个案例中，我们首先创建了一个FenwickTree类来实现树状数组的功能。在主函数中，我们首先构建了一个树状数组，并计算了不同区间的和。可以看到，树状数组可以高效地进行区间和的计算，时间复杂度为O(logN)。