用途
单点修改 查询前缀和
有时候会用到建多个树状数组的情况,所以我把建树状数组用的数组和数组长度作为参数。并且写了test函数。
既然是模板,就不再细述原理,读者可以查阅其他文章。建议参考书籍《算法竞赛进阶指南 李煜东》
代码
int lowbit(int x){
return x & -x;
}
void add(int x, int val, int *bit, int n){
// 让第x位加上val。bit是所用的数组,n是数组长度,下标从1开始哦
for (int i = x; i <= n; i += lowbit(i)){
bit[i] += val;
}
}
int sum (int x, int *bit, int n){
// 求x的前缀和,bit是所用的数组,n是数组长度,下标从1开始哦
int ret = 0;
for (int i = x; i > 0; i -= lowbit(i)){
ret += bit[i];
}
return ret;
}
void TestBinaryIndexedTree(){
int n, m, a[1000], x, y, z; //
cin >> n >> m; //n是数组长度,m是操作次数
for (int i = 1; i <= n; i++) a[i] = 0; // 初始化为0
for (int i = 1; i <= n; i++){
cin >> x;
add(i, x, a, n);
}
for (int i = 1; i <= m; i++){
cin >> x >> y >> z;
// x = 1代表把第y个数加z
// x = 2代表查询区间y到z的元素和
if (x == 1){
add(y, z, a, n);
}
else if (x == 2){
cout << sum(z, a, n) - sum(y - 1, a, n) << endl;
}
}
}