树状数组

  树状数组这个东西，因为它没有线段树的功能强大，所以在很多时候大家都不怎么用它。

但是树状数组有个好处就是它代码比较简单

嗯，，在洛谷上树状数组有专门的模板题

一个是单点修改，区间查询

嗯，直接附代码吧

#include<iostream>
#include<cstdio>

using namespace std;

int t[500010];
int n,m;

int lowbit(int x ){
	return x&(-x);
}

void add(int x,int k ){
	while(x<=n)
	{
		t[x]+=k;
		x+=lowbit(x);
	}
}

int query( int y ){
	   int sum=0;
	while(y>0)
	{
	    	sum+=t[y];
	    	y-=lowbit(y);
	}	
	return sum;
}



int main(){
	cin>>n>>m;

	for(int i=1;i<=n;i++)
	{	int a;
		scanf("%d",&a);
		add(i,a);  
	}
	  
	for(int i=1;i<=m;i++){
		int z;
		scanf("%d",&z);
		if(z==1)
		{
			int x,k;
			scanf("%d%d",&x,&k);
		    add(x,k);
		}
		if(z==2)
		{
		    int  x,y;
		    scanf("%d%d",&x,&y);
		    cout<<query(y)-query(x-1)<<endl;
		}	
	}
	return 0;
}



//以下是我的第一次写的代码
/*#include<iostream>
#include<cstdio>
#include<cstring>       //树状数组单点修改，区间查询 
using namespace std;
int a[500010];
int t[500010];
int n,m;
int lowbit(int x){      //lowbit数组实际上用了二进制 
	return x& (-x);
} 
void add(int x,int k){  //给单点x加上k值 
	while(x<=n){
	t[x]+=k;             //给此后一直到n的数都加上k
	                     //因为t是树状数组，以便下面求和 
	                     // 也就是不断更新父节点的值 
	x+=lowbit(x);        //这里的x表示下标 ，所以是数组在逐渐向后 
	}
}
int sum(int x ){      //类似前缀和 
	int ans=0;
	while(x!=0){
		ans+=t[x];
		x-=lowbit(x);
	}
	return ans;
}
int main(){
    scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		int a;
		scanf("%d",&a);
		add(i,a);
	}
	for(int i=1;i<=m;i++){
		int k,x,y;
	    scanf("%d%d%d",&k,&x,&y);
		if(k==1)
		add(x,y);
		if(k==2)	
		printf("%d
",sum(y)-sum(x-1));
	}
	return 0;
}*/

　　

还有一种就是区间修改，单点查询

上代码

#include<iostream>
#include<cstdio>
using namespace std;

int a[500010];
int t[500010];
int n,m;

int lowbit(int x ){return x & ( -x );}


void add1 (int x ,int k){
	while(x<=n){
		t[x]+=k;
		x+=lowbit(x);
	}
}

void add2 (int x , int y , int k ){
		while(x<=n){
			t[x]+=k;
			x+=lowbit(x);
		}
		y=y+1;
		while(y<=n){
	  	  t[y]=t[y] - k; 
	  	  y+=lowbit(y);	
		}
}

int query( int x ){
	   int sum=0;
	   while(x>0){
	   	   sum+=t[x];
	   	   x-=lowbit(x);
	   }
	return sum;
}

int main()
{
	
	cin>>n>>m;
	for(int i=1 ; i<=n ; i++ ){
		
	    scanf("%d",&a[i]);
		add1(i,a[i]-a[i-1]);
	}
	
	for(int i=1;i<=m;i++){
		int z;
		scanf("%d",&z);
		if(z==1)
		{
		   int x,y,k;
		   scanf("%d%d%d",&x,&y,&k);
		    add2 (x , y , k );	
		}
		
		if(z==2)
		{
			int x;
			scanf("%d",&x);
			cout<<query(x)<<endl;
			
		}
	}
}




//第一次
/*#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m;
int t[500010];
int a[500010];
int lowbit(int x){
	return x & (-x);
}
void add(int x,int k){	
    
	while(x<=n){
	t[x]+=k; 
	x+=lowbit(x);
    }
    
}
int update(int l,int r,int k){
     		add(l,k);    
            add(r+1,-k);
}

int query(int x){
     int ans=0;
	 while(x>0){
	 	ans+=t[x];
	 	x-=lowbit(x);
	 }   	
	 return ans;
}
int main(){
    scanf("%d%d",&n,&m);
    int now=0;
    int a;
    for(int i=1;i<=n;i++){    
	scanf("%d",&a);
	add(i,a-now);
	now=a;
}
for(int i=1;i<=m;i++){
    	int flag;
    	scanf("%d",&flag);
    	if(flag==1){
    		int x,y,k;
    	    scanf("%d%d%d",&x,&y,&k);
			update(x,y,k);
    	}
    	if(flag==2){
    		int x;
    		scanf("%d",&x);
        printf("%d
",query(x));
    	}
    }
 
	return 0;
} */