模板题,没什么好说的。但是,数组要开4N!!!别像我一样RE三次

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 500050
using namespace std;

int n,m,ans,cnt;
int a[M<<2];

struct tree{
	int l,r,da;
}tr[M<<2];

void Build(int l,int r,int x){//建树 
	cnt++;
	tr[x].l=l;
	tr[x].r=r;
	if(l==r)
		return ;
	int mid=(l+r)>>1;
	Build(l,mid,x<<1);
	Build(mid+1,r,x<<1|1);
}

inline int Add(int x){//加点 
	if(tr[x].l==tr[x].r){
		tr[x].da=a[tr[x].r];
		return tr[x].da;
	}
	tr[x].da=Add(x<<1)+Add(x<<1|1);
	return tr[x].da;
}

void Plus(int x,int dis,int k){//区间修改 
	tr[x].da+=k;
	if(tr[x].l==tr[x].r)
		return ;
	if(dis<=tr[x<<1].r)
		Plus(x<<1,dis,k);
	if(dis>=tr[x<<1|1].l)
		Plus(x<<1|1,dis,k);
}

void Search(int x,int l,int r){//区间查找 
	if(tr[x].l>=l && tr[x].r<=r){
		ans+=tr[x].da;
		return ;
	}
	if(tr[x<<1].r>=l)
		Search(x<<1,l,r);
	if(tr[x<<1|1].l<=r)
		Search(x<<1|1,l,r);
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	Build(1,n,1);
	Add(1);
	for(int i=1;i<=m;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		if(x==1)
			Plus(1,y,z);
		else{
			ans=0;
			Search(1,y,z);
			printf("%d\n",ans);
		}
	}
	return 0;
}

 

0 0 votes
文章评分

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据

0 评论
Inline Feedbacks
View all comments