树形数组模板代码及其注释

//树形数组
//树形数组是一种数据结构，可以用来高效地维护数组的前缀和，支持单点修改和区间查询
//树形数组的操作时间复杂度为O(logN)，比线性的暴力算法要快很多

#include <iostream>
#include <vector>

using namespace std;

//树形数组的实现
class FenwickTree {
public:
FenwickTree(int n) {
tree.resize(n + 1); //树形数组的大小为n+1
}

//单点修改，将i位置上的值加上val
void update(int i, int val) {
while (i < tree.size()) {
tree[i] += val; //更新树形数组的值
i += lowbit(i); //更新i的值
}
}

//区间查询，查询区间[1, i]上的和
int query(int i) {
int sum = 0;
while (i > 0) {
sum += tree[i]; //累加区间[1, i]上的和
i -= lowbit(i); //更新i的值
}
return sum;
}

private:
vector<int> tree; //树形数组
//lowbit函数用于计算一个数的二进制表示中的最低位1所代表的值
int lowbit(int x) {
return x & -x;
}
};

int main() {
int n;
cin >> n;
FenwickTree tree(n); //创建一个大小为n的树形数组
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
tree.update(i, x); //将第i个位置上的值设置为x
}
int q;
cin >> q;
while (q--) {
int op, x, y;
cin >> op >> x >> y;
if (op == 1) {
tree.update(x, y); //将第x个位置上的值加上y
} else {
cout << tree.query(y) - tree.query(x - 1) << endl; //查询区间[x, y]上的和
}
}
return 0;
}