树状数组
树状数组是一种可以快速区间操作的算法，与差分不同的是，树状数组是在线，和线段树一样，而差分则是离线。下面我就来讲一讲。
1.简介
树状数组一共有3个步骤，分别是：lowbit、增加结点数值、查询，并且附有main函数。
2.代码
1.lowbit
int lowbit(int x){
return x & -x;
}
2.增加结点数值
int n, tree[100005];//n和树状数组
void add(int x, int v){//x为增加数值的结点编号，v为增加的数值
while (x <= n){
t[x] += v;
x += lowbit(x);
}
}
3.查询
int check(int x){
int sum = 0;
while (0 < x){
sum += t[x];
x -= lowbit(x);
}
return sum;
}
附.main
int main(){
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++){
int x;
cin >> x;
add(i, x);
}
for (int i = 1; i <= n; i++){
int x, y;
string s;
cin >> s >> x >> y;
if ("add" == s) add(x, y);//增加
else cout << check(y) - check(x-1) << endl;//查询
}
return 0;
}
这就是树状数组的全部了，点个赞呗。欢迎在评论区留言！
c++算法大全 文章被收录于专栏
本专栏收集了c++大部分基础算法，附有简介和代码。
