【樹狀數組】

問題的提出：是否可以用線性數據結構的方法解決動態統計子樹權和的問題呢？?有的，樹狀數組。

假設當前數組為a[]，元素個數為n。

1. 子區間的權和數組為sum，那么數組a[]中 i 到 j這段區間的數組元素和為sum[i,j]=?a[k]的累加 【k屬于(i->j)】

2. 現在定義前綴和數組s[]，s[i]代表從a[i]---a[i]的和，那么又可以這樣表示 sum[i,j] = s[j]-s[i-1].

3. lowbit(k)為整數k的二進制表示中?右邊第一個1所代表的數字，lowbit(k)=k&(-k).

4.?樹狀數組為c[]，c[k]存儲的是從a[k]開始向 低的下標那邊數lowbit(k)個元素之和，一層遍歷。

注意：我們要把a[]數組的元素從下標1開始存儲.

這里列舉一下：

c[1]=a[1];???????????????????????????????????????????????????????????? s[1]=c[1];

c[2]=a[2]+a[1];???????????????????????????????????????????????????? s[2]=c[2];

c[3]=a[3];???????????????????????????????????????????????????????????? s[3]=c[3]+c[2];

c[4]=a[4]+a[3]+a[2]+a[1];??????????????????????????????????? s[4]=c[4];

c[5]=a[5];???????????????????????????????????????????????????????????? s[5]=c[5]+c[4];

c[6]=a[6]+a[5];??????????????????????????????????????????????????? s[6]=c[6]+c[4];

c[7]=a[7];???????????????????????????????????????????????????????????? s[7]=c[7]+c[6]+c[4];

c[8]=a[8]+a[7]+a[6]+a[5]a[4]+a[3]+a[2]+a[1];??? s[8]=c[8];

c[9]=a[9];???????????????????????????????????????????????????????????? s[9]=c[9]+c[8];

?

5.?計算每個s[i]的復雜度是O( log2(n) ).

6.?代碼：

#include <stdio.h>
#include <string.h>int a[101];
int c[101];
int s[101];int lowbit(int x)
{return x&(-x);
}int sum(int x)
{int s=0;while(x>0){s+=c[x];x=x-lowbit(x);}return s;
}int main()
{int i, j, k;for(i=1; i<=10; i++)a[i]=i;//創建a[]數組for(i=1; i<=10; i++){//計算每個c[i]c[i]=0;//c[i]從初始為0for(j=i-lowbit(i)+1; j<=i; j++){c[i]+=a[j];}}for(i=1; i<=10; i++){s[i]=sum(i);//計算i的前綴數組和}return 0;
}

?