树状数组——求和问题题解

program zht;
var
n,i,j,t,x,y,m:longint;
q,w:int64;
a,c:array[0..20000] of int64;

begin
assign(input,‘sum.in‘);
assign(output,‘sum.out‘);
reset(input);
rewrite(output);
readln(n);
for i:=1 to n do
read(a[i]);

for i:=1 to n do
begin
t:=i and (-i);
 for j:=i-t+1 to i do
 c[i]:=c[i]+a[j];
end;  // jian shu

t:=0;

readln(m);

for i:=1 to m do
begin
 readln(x,y);
 if x+y=0 then begin writeln(‘0‘); continue; end;
 q:=0;
 w:=0;
 t:=x-1;
  while t>0  do
   begin
   q:=q+c[t];
   t:=t-(t and (-t));
   end;
  t:=y;

  while t>0 do
  begin
  w:=w+c[t];
  t:=t-(t and (-t));
  end;

  writeln(w-q);
end;

close(input);
close(output);

end.