什么是树状数组？？？
树状数组就是把一个一般的数组弄成一个像树一样的结构！
如图：（图片来自百度）
刚开始是数组A，经过变换后，C[1]=A[1], C[2]=A[1]+A[2],C[3]=A[3],C[4]=A[1]+A[2]+A[3]+A[4] 等等；
为什么要把好好的数组变成这样呢？
这要从树状数组所要解决的问题说起，树状数组所要解决的就是求数组某一个区间的和的问题，如果不用树状数组，而用一般的方法，解决这样的问题，我们就要在给定的区间中循环累加，需要求几个区间的和就必须循环几次，显然，如果数据比较多，这种做法耗费的时间肯定比较多。
我们有可能还会想到另一种方法，就是把该数组中的各个区间的和先求出来，存放到另一个数组中，这样求区间和的时候就可以直接使用，但是用这种方法还用一个问题，就是当我们改变数组中的某个值时，存放区间和的那个数组就需要很大的改动，比如：两个数组A[100](原数组) ， B[100](存放区间和的数组) ，如果A[4]的值改变了，那么在B数组中 A[1]+A[2]+A[3]+A[4] ,A[2]+A[3]+A[4] ,A[3]+A[4], A[4]+A[5] ,A[4]+A[5]+A[6]等等和A[4]有关的和都要改变，这就增加了时间的复杂度。
为了解决这些问题，树状数组应运而生了，如上图所示这种数据结构也是把数组的区间和存到数组中（可以是本数组），但是这些区间和存放的是一个树形的结构，弄成树形结构的目的是什么呢？弄成树形结构的目的就是解决改变数组中的值得时候能够减少区间和的更新次数。
树状数组的思想说完了，接下来说一下它的原理：
根据上图人们总结出了一个规律：
C[1]=A[1] ;
C[2]=A[1]+A[2];
C[3]=A[3];
C[4]=A[1]+A[2]+A[3]+A[4];
C[5]=A[5];
C[i]= ？；
这些式子有什么规律呢？C[i]又等于多少呢？
一些牛人发现，，C[i]等于多少，完全取决于 i 等于几，也就是我们把 i 转换为二进制，如2 = （10）（！从末尾向前查有1个0），那么C[2]后面就应该有2的一次方个元素，也就是2个元素，那究竟是从哪个元素到哪个元素呢？ 牛人们又发现元素区间和 i 还有关系，如C[2] = A[2-(2的k次方)+1]……A[2] (k代表2转换成2进制后从后向前查有多少个0)。
总结：C[i] 所代表的区间和为：A[i-2的k次方+1]…….A[i];(k和上面的意义一样)；
怎么弄求出k呢？是不是想着先把 i 转换成2进制，然后存放到数组中，然后从后向前遍历，求出0的个数。
其实又有一些牛人替我们解决了这个问题，人家只用一段很短的代码就直接求出了2的k次方：
一，int liw(int i)
{
return i&(-i);
}
二，int liw(int i)
{
return i&(i^(i–1));
}
两种方法结果都一样，都是求出2的k次方！
怎么求前 i 项的和呢？
int sum(int i)
{
int s=0;
while(i>0)
{
s=s+C[i];
i=i-liw(i);//这句代码可以看图自己手写运行一遍
}
}
最后就是更新数组的值了。
void add(int i , int v)//对数组中第i个元素加v
{
while(i<=m)//m是数组的长度
{
C[i]=C[i]+v;
i=i+liw(i);//自己对照上图运行
}
}
树状数组的核心思想差不多就是这么多，下面有两个题，帮助大家理解树状数组！
一. 给定一个数组，求数组中某个区间的和。
输入：m,n 分别表示数组中的元素个数，和区间数；
输出：每个区间的和；
#include<stdio.h>
int m,n;
int c[1000]={0};
int liw(int i)
{
return i&(-i);
}
void add(int i , int v)//对数组中第i个元素加v
{
while(i<=m)//m是数组的长度
{
C[i]=C[i]+v;
i=i+liw(i);//自己对照上图运行
}
}
int sum(int i)
{
int s=0;
while(i>0)
{
s=s+C[i];
i=i-liw(i);//这句代码可以看图自己手写运行一遍
}
}
int main(void)
{
int s,con,x,y;
for(int i=1;i<=m;i++)
{
scanf("%d",&s);
add(i,s);//在此是创建树状数组，因为刚开始数组元素为0
}
for(int k=1;k<=n;k++)
{
scanf("%d%d",&x,&y);
con=sum(y)-sum(x-1);
printf("%d\n",con);
}
return 0;
}
这是最简单的树状数组的应用！
更多的应用可以看nyoj《士兵杀敌》问题！
望着它们，我睡着了。今天已经过去——我生命中所有天中的一天，
