var a:array[0..15,0..15000]of longint;
    i,j,k,n,m,h:longint; f1, f2:text;
    tip,x,y:integer;

procedure scade(z,v:integer);
var i,k:longint;
begin
  k:=z;
  for i:=0 to h do
  begin
    dec(a[i,k],v);
    k:=k div 2 + k mod 2;
  end;
end;

function sum(x:integer):longint;
var s:longint; v,i:integer;
begin
   s:=0; i:=0; v:=x;
   while true do
   begin
     if v mod 2=1 then s:=s+a[i,v];
     if v = 1 then break;
     v:=v div 2;
     inc(i);
   end;
   sum:=s;
end;

procedure showa;
var k,i,j:longint;
begin
  k:=n; i:=0;
  while true do
  begin
    for j:=1 to k do write(a[i,j],' ');
    writeln;
    if k=1 then break;
    k:=k div 2 + k mod 2; inc(i);
  end;
end;

begin
  assign(f1, 'datorii.in');
  reset(f1);
  assign(f2, 'datorii.out');
  rewrite(f2);

  fillchar(a, sizeof(a),0);
  
  readln(f1, n,m);
  for j:=1 to n do read(f1, a[0,j]);
  
  k:=n div 2; i:=1;
  while true do
  begin
    for j:=1 to k do a[i,j]:=a[i-1,j*2-1]+a[i-1, j*2];
    if k=1 then break;
    k:=k div 2 + k mod 2; inc(i);
  end;
  h:=i;
  
{  showa;}

  for i:=1 to m do
  begin
    readln(f1, tip, x,y);
    if tip = 0
    then begin
        scade(x,y);
        {showa;}
    end
    else begin
        writeln(f2, sum(y)-sum(x)+a[0,x]);
    end
  end;
  close(f1);
  close(f2);
  {readln;}
end.