program datorii;
var A,B : array [1..15000] of longint;
    f,g : text;
    n,j,x,p1,p2 : integer;
    S,i,m : longint;
function k2c(n:integer):integer;
begin
k2c := 0;
while n mod 2 = 0 do begin
k2c := k2c+1;
n := n div 2;
end;
end;

function k2(n:integer):integer;
begin
if n=0 then k2 := 1
else
if n=1 then k2 := 2
       else if n mod 2 = 0 then k2 := sqr(k2(n div 2))
                           else k2 := 2*sqr(k2(n div 2));
end;

function max(a,b:longint):longint;
begin
if a>b then max := a
        else max := b;
end;


procedure build;
var i,j : integer;
begin

for i := 1 to n do begin
B[i] := A[i];
for j := 1 to k2(k2c(i))-1 do
B[i] := B[i]+A[i-j];
end;
end;

procedure update(poz,val : integer);
begin

while poz<=n do begin
B[poz] := max(0,B[poz]-val);
poz := poz+k2(k2c(poz));
end;
end;

function sum(p:integer):longint;
begin
sum := 0;
while p>0 do begin
sum := sum + B[p];
p := p-k2(k2c(p));
end;
end;

begin
assign(f,'datorii.in');
reset(f);
assign(g,'datorii.out');
rewrite(g);

readln(f,n,m);

for i := 1 to n do
read(f,A[i]);
readln(f);
build;

for i := 1 to m do begin
readln(f,x,p1,p2);
if x=1 then begin
            S := sum(p2)-sum(p1-1);
            writeln(g,S)
            end
else update(p1,p2);
end;

close(f);
close(g);

end.