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

avatar
作者
筋斗云
阅读量:0

树状数组(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)。

广告一刻

为您即时展示最新活动产品广告消息,让您随时掌握产品活动新动态!