var a:array[0..16, 1..17000]of longint;
    i1,i,j,k1,k,n,m,tip,x,y:longint; f1, f2:text;

function log2(n:longint):longint;
var t:longint;
begin
  t:=0;
  while 1 shl t < n do inc(t);
  log2:=t;
end;

function sum(x:longint):longint;
var s,p,i:longint;
begin
   s:=0; p:=x; i:=0;
   while p>0 do
   begin
      if p mod 2 = 1
      then s:=s+a[i,p];
      p:=p div 2;
      inc(i);
   end;
   sum:=s;
end;
    
begin
  assign(f1, 'datorii.in');
  reset(f1);
  assign(f2, 'datorii.out');
  rewrite(f2);
  
  readln(f1, n,m);
  for i:=1 to n do read(f1, a[0,i]);
  
  k:=log2(n);
  for j:=1 to k do
    for i:=1 to n shr j do
       a[j,i]:=a[j-1,i*2]+a[j-1,i*2-1];
       
  {
  for j:=0 to k do
  begin
    for i:=1 to n shr j do write(a[j,i], ' ');
    writeln;
  end;
   }
   
  for i1:=1 to m do
  begin
    readln(f1, tip, x,y);
    if tip = 0
    then begin
       for k1:=0 to k do
       begin
         dec(a[k1, x], y);
         x:=(x-1) div 2 + 1;
       end;
       {
       for j:=0 to k do
       begin
         for i:=1 to n shr j do write(a[j,i], ' ');
         writeln;
       end;
       }
    end
    else begin
        writeln(f2, sum(y)-sum(x-1));
    end
  end;
  {
  for j:=0 to k do
  begin
    for i:=1 to n shr j do write(a[j,i], ' ');
    writeln;
  end;
  }
  close(f1);
  close(f2);
end.