var     a,c:array[1..15000] of integer;
        b:array[1..15000] of integer;
        d:array[0..15] of integer;
        m,n,i,j,x,y,k,sum:longint;
        f1,f2:text;
begin
assign(f1,'datorii.in');
assign(f2,'datorii.out');
reset(f1);
rewrite(f2);
readln(f1,n,m);
for i:=1 to n div 2 do
  begin
    if c[i]=0 then
      begin
      j:=i;
      while j<=n do
        begin
          c[j*2]:=c[j]+1;
          j:=j*2;
        end;
      end;
  end;
d[0]:=1;
for i:=1 to 14 do
  d[i]:=d[i-1]*2;

for i:=1 to n do
  begin
    read(f1,a[i]);
    for j:=i-d[c[i]]+1 to i do
      b[i]:=b[i]+a[j];
  end;

for i:=1 to m do
  begin
    readln(f1,j,x,y);
    if j=0 then
    begin
      k:=x;
      while k<=n do
        begin
          b[k]:=b[k]-y;
          inc(k,d[c[k]]);
        end;
    end else
    begin
      k:=y;
      sum:=0;
      while k>0 do
        begin
        sum:=sum+b[k];
        dec(k,d[c[k]]);
        end;
      k:=x-1;
      while k>0 do
        begin
        sum:=sum-b[k];
        dec(k,d[c[k]]);
        end;
      writeln(f2,sum);
    end;
  end;
close(f1);
close(f2);
end.