树状数组(Binary
Indexed Tree(BIT), Fenwick Tree)是一个查询和修改复杂度都为log(n)的数据结构。主要用于查询任意两位之间的所有元素之和，但是每次只能修改一个元素的值；经过简单修改可以在log(n)的复杂度下进行范围修改，但是这时只能查询其中一个元素的值。
树状数组和线段树很像，但能用树状数组解决的问题，基本上都能用线段树解决，而线段树能解决的树状数组不一定能解决。相比较而言，树状数组效率要高很多。
据图可知：c1=a1，c2=a1+a2，c3=a3，c4=a1+a2+a3+a4，c5=a5，c6=a5+a6，c7=a7，c8=a1+a2+a3+a4+a5+a6+a7+a8，c9=a9，c10=a9+a10，c11=a11........c16=a1+a2+a3+a4+a5+.......+a16。
分析上面的几组式子可知，当 i 为奇数时，ci=ai ；当 i 为偶数时，就要看 i 的因子中最多有二的多少次幂，
例如，6（110） 的因子中有 2 的一次幂，等于 2 ，所以 c6=a5+a6（由六向前数两个数的和），4（100）的因子中有
2 的两次幂，等于 4 ，所以 c4=a1+a2+a3+a4（由四向前数四个数的和）。
（一）有公式：cn=a(n-a^k+1)+.........+an
（其中 k 为 n 的二进制表示中从右往左数的 0 的个数，就是最后一个1的位置）。
例如,Lowbit(34)的返回值将是2；而Lowbit(12)返回4；Lowbit(8)返回8。
将34转为二进制,为0010 0010,这里的"最后一个1"指的是从
位往前数,见到的第一个1,也就是
位上的1.
程序上，((Not I)+1) And I表明了最后一位1的值,
仍然以34为例,Not 0010 0010的结果是 1101 1101(221),加一后为1101 1110(222), 把0010
0010与1101 1110作AND,得0000 0010(2).
lowbit（）的返回值就是 2^k 次方的值。
int lowbit(int x)
{
return x&(-x);
}
求出来 2^k 之后，数组 c 的值就都出来了，接下来我们要求数组中所有元素的和。
（二）求数组的和的算法如下：
（1）首先，令sum=0，转向第二步；
（2）接下来判断，如果 n>0 的话，就令sum=sum+cn转向第三步，否则的话，终止算法，返回 sum 的值；
（3）n=n - lowbit（n）（将n的二进制表示的最后一个零删掉），回第二步。
int Sum(int n)
{
int sum=0;
while(n>0)
{
sum+=c[n];
n=n-lowbit(n);
}
return sum;
}
（三）当数组中的元素有变更时，树状数组就发挥它的优势了，算法如下（修改为给某个节点 i 加上 x ）：
（1）当 i<=n 时，执行下一步；否则的话，算法结束;
（2）ci=ci+x ，i=i+lowbit（i）（在 i 的二进制表示的最后加零），返回第一步。
void change(int i,int x)
{
while(i<=n)
{
c[i]=c[i]+x;
i=i+lowbit(i);
}
}
（四）复杂度
初始化复杂度最优为O(N)
单次询问复杂度O(\log N),其中N为数组大小
单次修改复杂度O(\log N),其中N为数组大小
空间复杂度O(N)
附HDOJ 1892 二维的
void add(int x,int y,int d)//d是要增加的值
{
int i,j;
for(i=x;i<N;i+=(i&-i))
for(j=y;j<N;j+=(j&-j))
map[i][j]+=d;
}
int sum(int x,int y)
{
int i,j,ans=0;
for(i=x;i>0;i-=(i&-i))
for(j=y;j>0;j-=(j&-j))
ans+=map[i][j];
return ans;
}