Cod sursa(job #518380)

Utilizator blastoiseZ.Z.Daniel blastoise Data 31 decembrie 2010 13:03:32
Problema Datorii Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <stdio.h>

int N,M,i,x,a,b;
int T[32768];

inline void add(int nod,int L,int R,int day,int val)
{
	int M=(L+R)/2;

	if(L==day&&R==day) T[nod]+=val;
	else
	{
		if(day<=M) add(2*nod,L,M,day,val);
		else add(2*nod+1,M+1,R,day,val);
		T[nod]=T[2*nod]+T[2*nod+1];
	}
}

inline int que(int nod,int L,int R)
{
	int M=(L+R)/2;
	int sol=0;

	if(a<=L&&R<=b) return T[nod];
	else
	{
		if(a<=M) sol=que(2*nod,L,M);
		if(b>M) sol+=que(2*nod+1,M+1,R);
		return sol;
	}
}

int main()
{
	freopen("datorii.in","r",stdin);
	freopen("datorii.out","w",stdout);

	scanf("%d%d",&N,&M);
	for(i=1;i<=N;i++)
	{
		scanf("%d",&x);
		add(1,1,N,i,x);
	}
	
	for(i=1;i<=M;i++)
	{
		scanf("%d%d%d",&x,&a,&b);
		if(x==0) add(1,1,N,a,-b);
		else printf("%d\n",que(1,1,N));
	}

	return 0;
}