这几天一直学习树状数组，可是还是一知半解。

 如果给定一个数组，要你求里面所有数的和，一般都会想到累加，但是当那个数组很大的时候，累加就显得太耗时了，时间复杂度为O（n）,并且采用累加的方法还有一个局限，那就是，当改掉数组中的某一个元素之后，仍然让你求数组中某段元素的和，就显得麻烦 了，所以我们就要用到树状数组，它到 时间复杂度为O(lgn)，相比之下就快的多，。下面就说一下什么是树状数组：

树状数组主要用到一个累加的思想，下面来看一下树状数组图，方便理解：

根据上图可知：

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
等等

分析上面的几组式子可知，当i为奇数时，ci=ai;

当i为偶数时，就要看i的因子中最多有二的多少次幂，例如，6的因子中有二的一次幂，等于2：

所以c6=a5+a6（由六向前数俩个数的和），4的因子中有二的俩次幂，，等于四，所以c4=a1+a2+a3+a4（由四向前数四个数的和）；

（1）有公式cn=a（n-a^k+1)+.....an(其中k为n的二进制表示中从右往左数的0的个数）

下面是求a^k方法：

<pre name="code" class="html"><pre name="code" class="html">int low(int n)
{
	return n&(-n);
}

low（）的返回值就是2^k次方的值。

求出2^k之后，数组c的值就都可以求出来了。接下来我们要求数组中所有元素的和。

（2）求数组的和的算法如下：

（a）首先，令sum=0，执行下一步；

（b）判断，如果n>0的话，就令sun=sum+cn，继续执行下一步，否则，终止算法，返回sum的值。

（c）n=n-low(n)(将n的二进制表示的最后一个零删掉），返回第二步继续执行。

代码实现：

<pre name="code" class="html">int sum(int n)
{
	int sum=0;
	while(n>0)
	{
		sum=sum+c[n];
		n=n-low(n);
	}
	return sum;
}

（3）当数组中的元素有改变时，树状数组就可以发挥它的优势了，算法如下：（数组改变时，是给某一个结点i加上x）

（b）c[i]=c[i]+x;i=i+low(i)(在i的二进制表示的最后加零），返回第一步。

代码实现：

<pre name="code" class="csharp">void change(int i,int x)
{
	while(i<=n)
	{
		c[i]=c[i]+x;
		i=i+low(i);
	}
}

树状数组