树状数组

用于求某一段的和，用于在修改数列中的一些项之后的某一段的和。

用于求 1~i 的最大值。

program ACRush;

var

a,c:array[0..200010] of longint;

v:array[0..200010] of boolean;

i,j,k,m,n,x,y:longint;

function lowbit(x:longint):longint;

begin

lowbit:=x and (-x);

end;//让这个数只有最靠后一个 1 保留，其余的全变成 0 （一个数变为负数：取反加一）在二进制时末尾0的个数，或者说是i用2的幂方和表示时的最小指数。

procedure add(k,x:longint);

begin

if k<=0 then exit;

while k<=n do

begin

inc(c[k],x);

inc(k,lowbit(k));

end;

end;//给数组中的某一个数加上一个数。

function find(k:longint):longint;

begin

find:=0;

if k=0 then exit(0);

if k=1 then exit(c[1]);

while k>0 do

begin

inc(find,c[k]);

dec(k,lowbit(k));

end;

end;//求数组中一段的和

begin

readln(n);

fillchar(c,sizeof(c),0); //树状数组

for i:=1 to n do

begin

read(a[i]); //初始数列

add(i,a[i]); //注意这个读入！！！

end;

readln;

readln(m);

for i:=1 to m do

begin

readln(y);

writeln(find(y)); //find 为 a[1]~a[y] 的和

end;

end.