# 树状数组

## 介绍

\$\$c_1=a_1——{(1)}_{10}={(1)}_2\$\$ \$\$c_2=a_2+c_1——{(2)}_{10}={(10)}_2\$\$ \$\$\ldots\$\$

## Code

`var    n, i: longint;    a, c: array [1..10000] of longint;//计算x最右边的1所代表的数字。//如：lowbit(0b1100)=0b100function lowbit(x: longint): longint;begin    lowbit := x and (-x);end;//给a[index]加上xprocedure add(index, x: longint);begin    inc(a[index], x);    while index<=n do    begin        inc(c[index], x);        inc(index, lowbit(index));    end;end;//求a[1~index]的和function sum(index: longint): longint;begin    sum := 0;    while index>0 do    begin        inc(sum, c[index]);        dec(index, lowbit(index));    end;end;var    s: longint;    op: longint;    x,y: longint;begin    assign(input, 'main.in'); reset(input);    assign(output, 'main.out'); rewrite(output);    readln(n);    for i := 1 to n do    begin        read(a[i]);        add(i, a[i]);    end;    while not eof do    begin        read(op);        if op = 1 then //添加操作        begin           read(x, y);           Add(x, y);        end        else           //求和操作        begin            read(s);            writeln(sum(s));        end;    end;    close(input); close(output);end.`

## OOPS!

A comment box should be right here...But it was gone due to network issues :-(If you want to leave comments, make sure you have access to disqus.com.