树状数组

心已赠人 2022-05-16 05:17 263阅读 0赞

树状数组单点修改，单点查询  
洛谷oj :[点我][Link 1]  
模板：

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    const int N=500000+5;
    int n,q;
    int a[N],tree[N];
    int lowbit(int x){
    	return x&(-x);
    }
    void update(int x,int val){
    	while(x<=n){
    		tree[x]+=val;
    		x+=lowbit(x);
    	}
    }
    int query(int x){
    	int sum=0;
    	while(x>0){
    		sum+=tree[x];
    		x-=lowbit(x);
    	}
    	return sum;
    }
    int main(){
    	scanf("%d%d",&n,&q);
    	for(int i=1;i<=n;i++){
    		scanf("%d",&a[i]);
    		update(i,a[i]);
    	}
    	while(q--){
    		int l,r;
    		int flag;
    		scanf("%d%d%d",&flag,&l,&r);
    		if(flag==1){
    			update(l,r);
    		}
    		else{
    			printf("%d\n",query(r)-query(l-1));
    		}
    	}
    }

树状数组区间修改，单点查询  
洛谷oj:[点我][Link 2]  
原来的数值存在a\[\]里面，tree\[i\]=a\[i\]-a\[i-1\];  
求a\[i\]时，a\[i\]=a\[i-1\]+tree\[i\]=a\[i-2\]+tree\[i\]+tree\[i-1\]=…=tree\[1\]+tree\[2\]+…tree\[i\];

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    const int N=500000+5;
    int n,q;
    int a[N],tree[N];
    int lowbit(int x){
    	return x&(-x);
    }
    void update(int x,int val){
    	while(x<=n){
    		tree[x]+=val;
    		x+=lowbit(x);
    	}
    }
    int query(int x){
    	int sum=0;
    	while(x>0){
    		sum+=tree[x];
    		x-=lowbit(x);
    	}
    	return sum;
    }
    int main(){
    	scanf("%d%d",&n,&q);
    	for(int i=1;i<=n;i++){
    		scanf("%d",&a[i]);
    		update(i,a[i]-a[i-1]);
    	}
    
    	while(q--){
    		int l,r,k;
    		int flag;
            scanf("%d",&flag);
    		if(flag==1){
    			scanf("%d%d%d",&l,&r,&k);
    			
    			update(l,k);
    			update(r+1,-k);
    		}
    		else{
    			int x;
    			scanf("%d",&x);
    			printf("%d\n",query(x));
    			
    		}
    	}
    }

[Link 1]: https://www.luogu.org/problemnew/show/P3374
[Link 2]: https://www.luogu.org/problemnew/show/P3368