樹狀數組
本文正體字版由OpenCC轉換
樹狀數組是一個優美小巧的數據結構，在很多時候可以代替線段樹。一句話概括就是，凡是樹狀數組可以解決的問題，線段樹都可以解決，反過來線段樹可以解決的問題，樹狀數組不一定能解決。
樹狀數組英文名稱爲Binary Index Tree，直譯過來就是二進制索引樹，我覺得二進制索引樹更能說明其本質。樹狀數組的本質就是一種通過二進制位來維護一個序列前i和的數據結構。
對於維護的序列A，定義C[i]=A[j+1]+...+A[i]，其中j爲i的二進制表示中把最右邊的1換成0的值。j的值可以通過lowbit求出，即i-lowbit(i)。
lowbit(a)爲2^(a的二進制表示末尾0的個數)。可以用下面式子求出
lowbit(a)=a&(~a+1)
或者根據補碼的性質簡化爲
lowbit(a)=a&(-a)
修改方式如下
void modify(int p,int delta)
{
while (p<=N)
{
C[p]+=delta;
p+=lowbit(p);
}
}
求前綴和如下
int sum(int p)
{
int rs=0;
while (p)
{
rs+=C[p];
p-=lowbit(p);
}
return rs;
}
BYVoid 原創講解，轉載請註明。
上次修改時間 2017-05-22