如何在C++中实现树状数组

树状数组（Binary Indexed Tree，BIT）是一种用于动态维护序列前缀和的数据结构，可以在O(logn)的时间复杂度内完成区间和的更新和查询操作。以下是在C++中实现树状数组的示例代码：

#include <iostream> #include <vector>  using namespace std;  class FenwickTree { private:     vector<int> tree;  public:     FenwickTree(int n) {         tree.resize(n + 1);     }      void update(int idx, int delta) {         while (idx < tree.size()) {             tree[idx] += delta;             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 tree(nums.size());      for (int i = 0; i < nums.size(); i++) {         tree.update(i + 1, nums[i]);     }      cout << "Prefix sum of first 3 elements: " << tree.query(3) << endl;     cout << "Prefix sum of elements in range [2, 5]: " << tree.query(5) - tree.query(1) << endl;      return 0; } 

在这个示例中，我们首先定义了一个FenwickTree类，用于实现树状数组的功能。在主函数中，我们创建了一个FenwickTree对象，并使用update方法更新了树状数组的值。最后，我们使用query方法查询了前缀和的结果。

这是一个简单的示例，实际应用中可以根据具体需求对树状数组进行进一步的封装和优化。