树状数组

树状数组是一种可以快速区间操作的算法，与差分不同的是，树状数组是在线，和线段树一样，而差分则是离线。下面我就来讲一讲。

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;
}

这就是树状数组的全部了，点个赞呗。欢迎在评论区留言！