Program Datorii;
const doi : array[0..14] of longint=(1,2,4,8,16,32,64,128,256,512,1024,
                                     2048,4096,8192,16384);
var Intrare,Iesire : text;
    S : array[1..15000,0..14] of longint;
    A : array[1..15000] of integer;
    N : integer;
    M : longint;

procedure DeschideFisiere;
begin
  assign(Intrare,'datorii.in');
  assign(Iesire,'datorii.out');
  reset(Intrare);
  rewrite(Iesire);
end;

procedure CitesteNMA;
var i : integer;
begin
  readln(Intrare,N,M);
  for i:=1 to N do read(Intrare,A[i]);
end;

procedure InchideFisiere;
begin
  close(Intrare);
  close(Iesire);
end;

procedure CalculeazaS;
var i,j : integer;
begin
  for i:=1 to N do S[i,0]:=A[i];
  for i:=1 to 14 do
   for j:=1 to N do
    if N-j+1<=doi[i-1] then S[j,i]:=S[j,i-1]
     else
      S[j,i]:=S[j,i-1]+S[j+doi[i-1],i-1];
end;

function log2(a : integer) : integer;
begin
  log2:=trunc(Ln(a)/Ln(2));
end;

function Suma(a,b : integer) : longint;
var l,lg2 : integer;
begin
  if a<=b then
   begin
     l:=b-a+1;
     lg2:=log2(l);
     Suma:=S[a,lg2]+Suma(a+doi[lg2],b);
   end
   else Suma:=0;
end;

function max(a : integer) : integer;
begin
  if a>0 then max:=a else max:=1;
end;

procedure Achita(T,V : integer);
var i,j : integer;
begin
  for i:=0 to 14 do
   for j:=max(T-doi[i]+1) to T do S[j,i]:=S[j,i]-V;
end;

procedure Proceseaza;
var i : longint;
    op,n1,n2 : integer;
begin
  for i:=1 to M do
   begin
     readln(Intrare,op,n1,n2);
     if op=0 then Achita(n1,n2)
      else writeln(Iesire,Suma(n1,n2));
   end;
end;

begin
  DeschideFisiere;
  CitesteNMA;
  CalculeazaS;
  Proceseaza;
  InchideFisiere;
end.