那么,何為樹形數(shù)組呢??
下圖中的C數(shù)組就是樹狀數(shù)組,a數(shù)組是原數(shù)組;
![]()
可以發(fā)現(xiàn)這些規(guī)律:
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，我們設(shè)一個(gè)數(shù)組C定義C[t] = a[t – 2^k + 1] + … + a[t]，k為t在二進(jìn)制下末尾0的個(gè)數(shù)。
K的計(jì)算可以這樣:
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
所以問題變的很簡單,重要寫幾個(gè)函數(shù)就可以了;
求2^k的函數(shù)代碼如下:
int Lowbit(int t)
{
????return t & ( t ^ ( t - 1 ) );
}
|
求1 -- end和的函數(shù)代碼如下:
int Sum(int end)
{
????int sum = 0;
????while(end > 0)
????{
????????sum += in[end];
????????end -= Lowbit(end);
????}
????return sum;
}
|
對某位進(jìn)行操作函數(shù)如下(以加法為例)
void plus(int pos , int num)
{
????while(pos <= n)
????{
??????????in[pos] += num;
??????????pos += Lowbit(pos);
????}
}
|
有了這三個(gè)函數(shù)整個(gè)樹形數(shù)組也就基本構(gòu)建成功啦!!
對于剛才的一題,每次修改與詢問都是對C數(shù)組做處理.空間復(fù)雜度有3N降為N,時(shí)間效率也有所提高.編程復(fù)雜度更是降了不少.
下面是用樹狀數(shù)組做的 pku star
#include?<iostream>
using?namespace?std;
const?int?N?=?32100;
int?c[N];//樹狀數(shù)組
int?lowBit(int?x)?
{
????return?x?&?(x?^?(x?-?1));
}
void?add(int?x,?int?k)?{?
????//a[x]?+=?k
????while?(x?<=?N)?{
????????c[x]?+=?k;
????????x?+=?lowBit(x);
????}
}
void?sub(int?x,?int?k)?{
????//a[x]?-=?k
????while?(x?<=?N)?{
????????c[x]?-=?k;
????????x?+=?lowBit(x);
????}
}
int?sum(int?x)?{
????//return?sum(1..x);
????int?ret?=?0;
????while?(x?>?0)?{
????????ret?+=?c[x];
????????x?-=?lowBit(x);
????}
????return?ret;
}
int?out[N];
int?f[N];
int?main()?{
????//pku2352
????int?i,?j,?k,?x,?y;
????int?n;
????
????scanf("%d",?&n);
????for?(i=0;?i<n;?i++)?{
????????scanf("%d%d",?&x,?&y);
????????x++;
????????add(x,1);
????????out[sum(x-1)?+?f[x]]++;
????????f[x]++;
????}
????for?(i=0;?i<n;?i++)?{
????????printf("%d\n",?out[i]);
????}
????
????system("pause");
????return?0;
}posted on 2007-03-01 22:02
豪 閱讀(1599)
評論(3) 編輯 收藏 引用 所屬分類:
數(shù)據(jù)結(jié)構(gòu)與算法