樹狀數組



何為樹形數組呢?? 
下圖中的C數組就是樹狀數組,a數組是原數組; 
 
可以發現這些規律: 
C1=a1 
C2=a1+a2 
C3=a3 
C4=a1+a2+a3+a4 
C5=a5 
…… 
C8=a1+a2+a3+a4+a5+a6+a7+a8 
…… 
C2^n=a1+a2+….+a2^n 

對于序列a，我們設一個數組C定義C[t] = a[t – 2^k + 1] + … + a[t]，k為t在二進制下末尾0的個數。 
K的計算可以這樣: 
2^k=t and (t xor (t-1)) 
以6為例 
               (6)10=(0110)2 
xor    6-1=(5)10=(0101)2 
                        (0011)2 
and          (6)10=(0110)2 
                        (0010)2 

所以問題變的很簡單,重要寫幾個函數就可以了; 
求2^k的函數代碼如下: 

int Lowbit(int t) 
{ 
    return t & ( t ^ ( t - 1 ) ); 
} 
 


求1 -- end和的函數代碼如下: 

int Sum(int end) 
{ 
    int sum = 0; 
    while(end > 0) 
    { 
        sum += in[end]; 
        end -= Lowbit(end); 
    } 
    return sum; 
} 
 


對某位進行操作函數如下(以加法為例) 

void plus(int pos , int num) 
{ 
    while(pos <= n) 
    { 
          in[pos] += num; 
          pos += Lowbit(pos); 
    } 
} 
 


有了這三個函數整個樹形數組也就基本構建成功啦!! 
對于剛才的一題,每次修改與詢問都是對C數組做處理.空間復雜度有3N降為N,時間效率也有所提高.編程復雜度更是降了不少. 

代碼如下:
#include<stdio.h>
typedef struct item
{
 int x,y;
}Co;
Co date[15003];
int result[15003];
void solve(int n)
{
 int i,j,count=0;
 memset(result,0,sizeof(result));
 for(i=n-1;i>=0;i--)
 {
  count=0;
  for(j=i-1;j>=0;j--)
  {
   if(date[j].x<=date[i].x)
   {
    count++;
   }
  }
  result[count]++;
 }
}
main()
{
 int i,n;
 scanf("%d",&n);
 for(i=0;i<n;i++)
 {
  scanf("%d%d",&date[i].x,&date[i].y);
 }
 solve(n);
 for(i=0;i<n;i++)
 {
  printf("%d\n",result[i]);
 }
}