利用C++樹(shù)狀數(shù)組解決區(qū)間查詢(xún)問(wèn)題

樹(shù)狀數(shù)組（Binary Indexed Tree）是一種用于高效處理區(qū)間查詢(xún)的數(shù)據(jù)結(jié)構(gòu)。在C++中，可以通過(guò)以下代碼實(shí)現(xiàn)樹(shù)狀數(shù)組：

#include <iostream>
#include <vector>

using namespace std;

class FenwickTree {
private:
    vector<int> tree;

public:
    FenwickTree(int n) {
        tree.resize(n + 1);
    }

    void update(int index, int val) {
        while (index < tree.size()) {
            tree[index] += val;
            index += (index & -index);
        }
    }

    int query(int index) {
        int sum = 0;
        while (index > 0) {
            sum += tree[index];
            index -= (index & -index);
        }
        return sum;
    }

    int rangeQuery(int left, int right) {
        return query(right) - query(left - 1);
    }
};

int main() {
    vector<int> nums = {1, 3, 5, 7, 9, 11, 13};

    FenwickTree fenwickTree(nums.size());
    for (int i = 0; i < nums.size(); i++) {
        fenwickTree.update(i + 1, nums[i]);
    }

    cout << "Sum of elements in range [2, 5]: " << fenwickTree.rangeQuery(2, 5) << endl;

    return 0;
}

在這段代碼中，我們首先定義了一個(gè)FenwickTree類(lèi)，其中包含了update和query兩個(gè)方法用于更新和查詢(xún)操作。在主函數(shù)中，我們創(chuàng)建了一個(gè)FenwickTree對(duì)象，將給定數(shù)組的元素依次插入到樹(shù)狀數(shù)組中。最后，我們可以使用rangeQuery方法查詢(xún)區(qū)間的和。