Skip to content

Instantly share code, notes, and snippets.

@tarawa
Created July 10, 2013 08:36
Show Gist options
  • Save tarawa/5964499 to your computer and use it in GitHub Desktop.
Save tarawa/5964499 to your computer and use it in GitHub Desktop.
TYVJ1661 (树状数组、Pascal)
const
maxn=100000;
var
f:array [0..maxn] of int64;
n,k,l,r,i:longint;
order:char;
tmp,x:int64;
function lowbit(x:longint):longint;
begin
exit(x and (x xor (x-1)));
end;
procedure add(l,r:longint; x:int64);
var
i,j:longint;
begin
for i:=l to r do
begin
j:=i;
while (j<=n) do
begin
inc(f[j],x);
inc(j,lowbit(j));
end;
end;
end;
function sum(l,r:longint):int64;
function sum_t(p:longint):int64;
begin
sum_t:=0;
while p>0 do
begin
inc(sum_t,f[p]);
dec(p,lowbit(p));
end;
end;
begin
exit(sum_t(r)-sum_t(l-1));
end;
begin
readln(n,k);
for i:=1 to n do
begin
read(tmp);
add(i,i,tmp);
end;
readln;
for i:=1 to k do
begin
read(order,l,r);
if order='C' then writeln(sum(l,r)) else
begin
read(x);
if order='-' then x:=-x;
add(l,r,x);
end;
readln;
end;
end.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment