樹狀數組(Binary Indexed Tree)是一種用于高效處理區間查詢的數據結構。在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 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;
}
在這段代碼中,我們首先定義了一個FenwickTree類,其中包含了update和query兩個方法用于更新和查詢操作。在主函數中,我們創建了一個FenwickTree對象,將給定數組的元素依次插入到樹狀數組中。最后,我們可以使用rangeQuery方法查詢區間的和。