#include <cstdio>
#define NMAX 100001
int N,M;
int e[NMAX];
void citire();
void schimbare();
void suma();
void pozitie();
int nrzero();
int interval();

int main()
{
	int iden,i2,nr;
	freopen("aib.in","r",stdin);
	freopen("aib.out","w",stdout);
	scanf("%d %d",&N,&M);
	citire();

	
	for(int i=1;i<=M;i++)
	{
		scanf("%d",&iden);
		if(iden==0)
			schimbare();
		else if(iden==1)
			suma();
		else
			pozitie();		
	}
	
	return 0;
}

void citire()
{
	int x;
	scanf("%d %d",&N,&M);
	for(int i=1;i<=N;i++)
	{
		scanf("%d",&x);
		e[i]=e[i]+x;
		i2=i;
		while(i2)
			i2>>1;
		while(i2<=i)
			i2<<1;
		while(i2<=N)
		{
			e[i2]=e[i2]+x;
			i2<<1;
		}		
	}
}

void schimbare()
{
	int a,b;
	scanf("%d %d",&a,&b);
	while(a<=N)
	{
		e[a]=e[a]+b;
		a<<1;
	}
		
}

void suma()
{
	int a,b,;
	scanf("%d %d",&a,&b);
	printf("%d\n",interval(b)-interval(a-1));
}

void pozitie()
{
	int a;
	scanf("%d",&a);
}

int put(int a)
{
	int nr=0,int p=1;
	while(!a%2)
	{
		a=a/2;
		nr++;
	}
	while(nr--)
		p=p*2;
	
	return p;
}

int interval(int a,int p)
{
	int s=0;
	while(a)
	{
		s=s+e[a];
		a=a-p;
		p=put(a);
	}
	return s;
}