program datorii;
 var w,aux:array [0..15001] of longint;
     k:array [1..15001] of byte;
     i,n,m,t,a,b,pos:longint;
     b1,b2:array [1..1 shl 15] of char;
     fi,fo:text;
procedure gen;
 var nr,i,x:longint;
begin
 for i:=1 to 15000 do begin
                       nr:=0; x:=i;
                        while x and 1=0 do begin inc(nr); x:=x shr 1; end;
                       k[i]:=nr;
                       end;
end;
procedure change(a,b:longint);
begin
 while a<=n do begin aux[a]:=aux[a]-b; a:=a+(1 shl k[a]); end;
end;
function sum(x:longint):longint;
 var s:longint;
begin
  s:=0;
 while x>0 do begin s:=s+aux[x]; x:=x-(1 shl k[x]); end;
  sum:=s;
end;
begin
 assign(fi,'datorii.in');
  assign(fo,'datorii.out');
  settextbuf(fi,b1); settextbuf(fo,b2);
 reset(fi); rewrite(fo);
 readln(fi,n,m);
  for i:=1 to n do begin
                     read(fi,w[i]); w[i]:=w[i]+w[i-1];
                     end; readln(fi); gen;
  for i:=1 to n do aux[i]:=w[i]-w[i-(1 shl k[i])];
   for i:=1 to m do begin
                    read(fi,t,a,b);
                     if t=0 then change(a,b)
                             else writeln(fo,sum(b)-sum(a-1));
                     end;
   close(fo);
end.