数据结构：树状数组

绝地灬酷狼 2021-12-07 10:45 322阅读 0赞

### 数据结构：树状数组 ###

*  单点修改，区间查询
 *  区间修改，单点查询
 *  区间修改，区间查询
 *  参考博客

# 单点修改，区间查询 #

# include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e2 +4;
    int c[maxn];
    //编号从1开始
    int lowbit(int n){ 
    	return n&(-n);
    }
    
    int update(int x,int value){ 
        for(int i=x;i<maxn;i+=lowbit(i))c[i]+=value;
    }
    
    int sum(int x){ 
    	int ans=0;
    	for(int i=x;i>0;i-=lowbit(i))ans+=c[i];
    	return ans;
    }
    
    int main(){ 
    	// 单点修改
    	int x,value;
    	update(x,value);
    	// 区间求和[l,r]
    	int l,r,s = sum(r)-sum(l-1);
    }

# 区间修改，单点查询 #

# include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e2 +4;
    int c[maxn];
    //编号从1开始
    int lowbit(int n){ 
    	return n&(-n);
    }
    
    int update(int x,int value){ 
        for(int i=x;i<maxn;i+=lowbit(i))c[i]+=value;
    }
    
    int sum(int x){ 
    	int ans=0;
    	for(int i=x;i>0;i-=lowbit(i))ans+=c[i];
    	return ans;
    }
    
    int main(){ 
    	// 对区间[l,r]修该，增加一个值
    	int l,r,value;
    	update(l,value),update(r+1,-value);
    	// 单点查询，求x的值
    	int x,value;
    	value=sum(x);
    }

# 区间修改，区间查询 #

# include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e2 +4;
    int c1[maxn];
    int c2[maxn];
    //编号从1开始
    int lowbit(int n){ 
    	return n&(-n);
    }
    
    int update(int x,int value){ 
        for(int i=x;i<maxn;i+=lowbit(i))c1[i]+=value,c2[i]+=x*value;
    }
    
    int sum(int x){ 
    	int ans=0;
    	for(int i=x;i>0;i-=lowbit(i))ans+=(x+1)*c1[i]-c2[i];
    	return ans;
    }
    
    int main(){ 
    	// 对区间[l,r]修该，增加一个值
    	int l,r,value;
    	update(l,value),update(r+1,-value);
    	// 区间查询，求[l,r]的和
    	sum(r)-sum(l-1);
    }

# 参考博客 #

[掌握树状数组~彻底入门][Link 1]  
[树状数组区间修改加区间查询][Link 2]  
[树状数组 数据结构详解与模板(可能是最详细的了)][Link 3]

[Link 1]: https://www.cnblogs.com/acgoto/p/8583952.html
[Link 2]: https://www.cnblogs.com/lcf-2000/p/5866170.html
[Link 3]: https://blog.csdn.net/bestsort/article/details/80796531