欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

树状数组的简单介绍和C++实现

程序员文章站 2022-07-07 15:46:51
...

有关树状数组,大家可以参考网上介绍,这里,我简单介绍一下树状数组的实现:
树状数组作用:可以用于区间查询和单点更新:
比如,查询数组中从下标为2到4的值的和,那么就可以用到区间查询,这里的区间查询函数可以计算从1-n的值,根据个人的需要,就可以利用区间查询来计算出自己需要的值;那么单点更新就是说:可以在某一位加上或者减去某一个数字,同时更新树状数组的值即可。
以上的功能实现都取决于这个树状数组C的建立。
那么C是如何建立的,大家可以在网上查到:
C[i]=A[i-2^ k+1]+A[i-2^k+2]+…+A[i];
其中,A[i]为原始数组,C为树状数组,其中的2^k 表示的就是A数组和C数组之间的关系,也即lowbit操作,具体的可以查看其它网页。

现在我们知道了其基本原理额可有的一些操作,那么我们就可以用它来解决问题,比如:http://acm.hdu.edu.cn/showproblem.php?pid=1166
树状数组的简单介绍和C++实现
那么这一题就可以直接用树状数组来解决

#include<iostream>
#include<memory.h>
using namespace std;
const int max_n=1e3;
const int INF=0x7fffffff;
//@author;hairu,wu
/*

http://acm.hdu.edu.cn/showproblem.php?pid=1166

1
10
1 2 3 4 5 6 7 8 9 10
Query 1 3
6
Add 3 6
Query 2 7
33
Sub 10 2
Add 6 3
Query 3 10
59
End
*/

int c[max_n];//树状数组,有效下标从1开始 

//计算2^k操作 
int lowbit(int x){
	return x&(-x);
}

//单点更新,将x位置的数字加上一个y,同时数组的最大下标为n,
//且x位置后序的也要同时更新 
void update(int x,int y,int n){
	for(int i=x;i<=n;i+=lowbit(i)){
		c[i]+=y;
	}
} 

//获取从1-x之间的和 
int getSum(int x){
	int ans=0;
	for(int i=x;i>0;i-=lowbit(i)){
		ans+=c[i];
	}
	return ans;
}

int main(){
	int t;
	int n;
	int x,y,z;
	string s;
	cin >> t;
	while(t--){
		cin >> n;
		memset(c,0,sizeof(c));
		for(int i=1;i<=n;i++){
			cin >> z;
			update(i,z,n);	//单点更新i位置 
		}
		while(true){
			cin >> s;
			if(s=="End"){
				break;
			}else if(s=="Add"){
				cin >> x>>y;
				update(x,y,n);
			}else if(s=="Sub"){
				cin >> x>> y;
				update(x,-y,n);
			}else if(s=="Query"){
				cin >> x>> y;
				cout<<getSum(y)-getSum(x-1)<<endl;
			}
		} 
	}
	return 0;
}
相关标签: 难题