如果給定一個(gè)數(shù)組，要你求里面所有數(shù)的和，一般都會(huì)想到累加。但是當(dāng)那個(gè)數(shù)組很大的時(shí)候，累加就顯得太耗時(shí)了，時(shí)間復(fù)雜度為O(n)，并且采用累加的方法還有一個(gè)局限，那就是，當(dāng)修改掉數(shù)組中的元素后，仍然要你求數(shù)組中某段元素的和，就顯得麻煩了。所以我們就要用到樹狀數(shù)組，他的時(shí)間復(fù)雜度為O（lgn），相比之下就快得多。下面就講一下什么是樹狀數(shù)組：

         一般講到樹狀數(shù)組都會(huì)少不了下面這個(gè)圖：

         下面來分析一下上面那個(gè)圖看能得出什么規(guī)律：

         據(jù)圖可知：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。

         分析上面的幾組式子可知，當(dāng) i 為奇數(shù)時(shí)，ci=ai ；當(dāng) i 為偶數(shù)時(shí)，就要看 i 的因子中最多有二的多少次冪，例如，6 的因子中有 2 的一次冪，等于 2 ，所以 c6=a5 a6（由六向前數(shù)兩個(gè)數(shù)的和），4 的因子中有 2 的兩次冪，等于 4 ，所以 c4=a1 a2 a3 a4（由四向前數(shù)四個(gè)數(shù)的和）。

        （一）有公式：cn=a(n-a^k 1) ......... an（其中 k 為 n 的二進(jìn)制表示中從右往左數(shù)的 0 的個(gè)數(shù)）。

         那么，如何求 a^k 呢？求法如下：

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

         求出來 2^k 之后，數(shù)組 c 的值就都出來了，接下來我們要求數(shù)組中所有元素的和。

         （二）求數(shù)組的和的算法如下：

         （1）首先，令sum=0，轉(zhuǎn)向第二步；

         （2）接下來判斷，如果 n>0 的話，就令sum=sum cn轉(zhuǎn)向第三步，否則的話，終止算法，返回 sum 的值；

         （3）n=n - lowbit（n）（將n的二進(jìn)制表示的最后一個(gè)零刪掉），回第二步。

          代碼實(shí)現(xiàn)：

         （三）當(dāng)數(shù)組中的元素有變更時(shí)，樹狀數(shù)組就發(fā)揮它的優(yōu)勢(shì)了，算法如下（修改為給某個(gè)節(jié)點(diǎn) i 加上 x ）：

         （1）當(dāng) i<=n 時(shí)，執(zhí)行下一步；否則的話，算法結(jié)束;

         （2）ci=ci x ，i=i lowbit（i）（在 i 的二進(jìn)制表示的最后加零），返回第一步。

          代碼實(shí)現(xiàn)：