阅读量:0
树状数组（Fenwick Tree）是一种用于高效处理动态区间和的数据结构，可以用来解决一些统计问题，比如求区间和、区间最大值、区间最小值等。在处理大规模数据时，树状数组可以帮助我们高效地进行数据统计和查询。
下面是一个使用C++实现树状数组的示例代码：
#include <iostream> #include <vector> using namespace std; // 树状数组的实现 class FenwickTree { public: FenwickTree(int n) { tree.resize(n + 1, 0); } void update(int index, int delta) { while (index < tree.size()) { tree[index] += delta; index += index & -index; } } int query(int index) { int sum = 0; while (index > 0) { sum += tree[index]; index -= index & -index; } return sum; } private: vector<int> tree; }; int main() { int n = 10; // 数据规模 FenwickTree tree(n); // 更新元素 tree.update(1, 2); tree.update(2, 3); tree.update(3, 5); // 查询区间和 cout << tree.query(3) << endl; // 输出：10 cout << tree.query(5) - tree.query(2) << endl; // 输出：8 return 0; } 在上面的示例代码中，我们实现了一个简单的树状数组类FenwickTree，并使用其来处理一些数据更新和求和操作。通过树状数组，我们可以高效地处理大规模数据，并快速进行数据统计和查询。
