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,1..15] of char;
    f,g:text;
procedure pta;
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 schimba(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(f,'datorii.in');
  assign(g,'datorii.out');
  settextbuf(f,b1);
  settextbuf(g,b2);
  reset(f);
  rewrite(g);
  readln(f,n,m);
  for i:=1 to n do
    begin
      read(f,w[i]);
      w[i]:=w[i]+w[i-1];
    end;
  readln(f);
  pta;
  for i:=1 to n do
    aux[i]:=w[i]-w[i-(1 shl k[i])];
  for i:=1 to m do
    begin
      read(f,t,a,b);
      if t=0 then
        schimba(a,b)
      else
        writeln(g,sum(b)-sum(a-1));
end;
close(f);
close(g);
end.