C++樹狀數(shù)組的編程實(shí)踐案例

樹狀數(shù)組（Binary Indexed Tree）是一種用來高效地處理動態(tài)區(qū)間和的數(shù)據(jù)結(jié)構(gòu)。下面是一個C++的樹狀數(shù)組的實(shí)現(xiàn)案例：

#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());

    // 構(gòu)建樹狀數(shù)組
    for (int i = 0; i < nums.size(); i++) {
        ft.update(i + 1, nums[i]);
    }

    // 查詢區(qū)間和
    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;
}

在這個案例中，我們首先創(chuàng)建了一個FenwickTree類來實(shí)現(xiàn)樹狀數(shù)組的功能。在主函數(shù)中，我們首先構(gòu)建了一個樹狀數(shù)組，并計算了不同區(qū)間的和?？梢钥吹?，樹狀數(shù)組可以高效地進(jìn)行區(qū)間和的計算，時間復(fù)雜度為O(logN)。