树状数组厌氧,哪里写假了吗
查看原帖
树状数组厌氧,哪里写假了吗
432183
JoeBiden2020楼主2021/10/2 14:37
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[2000001];
int lowbit(int x){
	return x&(-x);
}
int getsum(int x){
	int ans=0;
	for(register int i=x;i>0;i-=lowbit(i)){
		ans+=a[i];
	}
	return ans; 
}
int add(int x,int d){
	for(register int i=x;i<=n;i+=lowbit(i)){
		a[i]+=d;
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	int temp,op,x,y,k,last=0;
	for(register int i=1;i<=n;i++){
		cin>>temp;
		add(i,temp-last);
		last=temp;
	}
	for(register int i=1;i<=m;i++){
		cin>>op; 
		if(op==1){
			cin>>x>>y>>k;
			add(x,k);
			add(y+1,-k);
		}
		else{
			cin>>x;
			cout<<getsum(x)<<endl;
		}
	}
	return 0;
}
2021/10/2 14:37
加载中...