P3368 树状数组2

思路：

这道题要求实现区间加和和单点查询，利用一般的树状数组可能不行，所以需要考虑修改。

修改：

考虑差分，差分可以实现区间修改功能，修改差分数组等于修改改数组所管辖的区间。

考虑将差分数组存入树状数组，此时单点修改等价于区间修改，区间查询等于单点查询。

思路不难，开始代码。

code：

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int a[8000001];
int c[2000001];
int sum[2000001];
int lowbit(int x){
	return x&(-x);
} 
void add(int x,int k){
	while(x<=n){
		c[x]+=k;
		x+=lowbit(x);
	}
}
int get(int x){
	int ans=0;
	while(x>0){
		ans+=c[x];
		x-=lowbit(x);
	}
	return ans;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>sum[i];	
		a[i]=sum[i]-sum[i-1];
		add(i,a[i]);	
	}
	for(int i=1;i<=m;i++){
		int opt;
		cin>>opt;
		int x,y,k;
		if(opt==1){
			cin>>x>>y>>k;
			add(x,k);
			add(y+1,-k);
		} 
		else{
			cin>>x;
			cout<<get(x)<<endl;
		}
	}
    return 0;
}

文章操作

思路：

修改：

code：

相关推荐

评论

P3368 树状数组2