C++树状数组
2021-04-23 18:29
阅读：747
#include
#include using namespace std;
int lowbit(int n) {
return n - (n & (n - 1));
}
/**
* 原始数组的i位置增加v后，更新c数组
*/
void update(int n, int i, int v, int c[]) {
for (int k = i; k c[k] += v;
}
}
int getSum(int c[], int i) {
int sum = 0;
for (int k = i; k >= 1; k -= lowbit(k)) {
sum += c[k];
}
return sum;
}
int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
int c[9];
memset(c, 0, sizeof(c));
for (int i = 0; i update(9, i + 1, arr[i], c);
}
cout cout cout
return 0;
}
评论
亲，登录后才可以留言！