萌新刚学OI,求助树状数组
查看原帖
萌新刚学OI,求助树状数组
338786
mushroom_knight楼主2020/6/2 15:27

RT,没发现哪里有问题/kk

但死活过不去、、、、、

#include<bits/stdc++.h>
using namespace std;
long long t[600001];
long long a[500001];
long long n,m;
int lowbit(int i){
	return i&-i;
}
void modify(int x,long long y){
	for(register int i=x;i<=n;i+=lowbit(i)){
		t[i]+=y;
	}
}
int find(long long x){
	long long ans=0;
	for(register int i=x;i;i-=lowbit(i)){
		ans+=t[i];
	}
	return ans;
}
void init(){
	for(register int i=1;i<=n;++i){
		modify(i,a[i]);
	}
}
int cmd,x,y,k;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(register int i=1;i<=n;++i){
		cin>>a[i]; 
	}
	init();
	for(register int i=1;i<=m;++i){
		cin>>cmd;
		if(cmd==1){
			cin>>x>>y>>k;
			modify(x,k);
			modify(y+1,-k);
		} 
		else{
			cin>>x;
			cout<<find(x)<<endl;
		}
	}
	return 0;
}

sos

2020/6/2 15:27
加载中...