樹狀數(shù)組（Fenwick tree，又名binary indexed tree），是一種很實(shí)用的數(shù)據(jù)結(jié)構(gòu)。它通過用節(jié)點(diǎn)i，記錄數(shù)組下標(biāo)在[ i –2^k + 1, i]這段區(qū)間的所有數(shù)的信息（其中，k為i的二進(jìn)制表示中末尾0的個(gè)數(shù)，設(shè)lowbit(i) = 2^k），實(shí)現(xiàn)在O(lg n) 時(shí)間內(nèi)對(duì)數(shù)組數(shù)據(jù)的查找和更新。
樹狀數(shù)組的傳統(tǒng)解釋圖，不能很直觀的看出其所能進(jìn)行的更新和查詢操作。其最主要的操作函數(shù)lowbit(k)與數(shù)的二進(jìn)制表示相關(guān)，本質(zhì)上仍是一種二分。因而可以通過二叉樹，對(duì)其進(jìn)行分析。事實(shí)上，從二叉樹圖，我們對(duì)它所能進(jìn)行的操作和不能進(jìn)行的操作一目了然。
和前面提到的點(diǎn)樹類似，先畫一棵二叉樹，然后對(duì)節(jié)點(diǎn)中序遍歷（點(diǎn)樹是采用廣度優(yōu)先），每個(gè)節(jié)點(diǎn)仍然只記錄左子樹信息，見圖：
由于采用的是中序遍歷，從節(jié)點(diǎn)1到節(jié)點(diǎn)k時(shí)，剛好有k個(gè)葉子被統(tǒng)計(jì)。
可以證明：
葉子k，一定在節(jié)點(diǎn)k的左子樹下。
以節(jié)點(diǎn)k為根的樹，其左子樹共有葉子lowbit(k)
節(jié)點(diǎn)k的父節(jié)點(diǎn)是：k + lowbit(k) 或 k - lowbit(k)
節(jié)點(diǎn)k + lowbit(k) 是節(jié)點(diǎn)k的最近父節(jié)點(diǎn)，且節(jié)點(diǎn)k在它的左子樹下。
節(jié)點(diǎn)k - lowbit(k) 是節(jié)點(diǎn)k的最近父節(jié)點(diǎn)，且節(jié)點(diǎn)k在它的右子樹下。
節(jié)點(diǎn)k，統(tǒng)計(jì)的葉子范圍為：(k - lowbit(k), k]。
節(jié)點(diǎn)k的左孩子是：k - lowbit(k) / 2
下面分析樹狀數(shù)組兩面主要應(yīng)用：
1 更新數(shù)據(jù)x，進(jìn)行區(qū)間查詢。
2 更新區(qū)間，查詢某個(gè)數(shù)。
由于，樹狀數(shù)組只統(tǒng)計(jì)了左子樹的信息，因而只能查詢更新區(qū)間[1, x]。只在在滿足[x,y]的信息可以由[1,x-1]和[1,y]的信息推導(dǎo)出時(shí)，才能進(jìn)行區(qū)間[x,y]的查詢更新。這也是樹狀數(shù)組不能用于任意區(qū)間求最值的根本原因。
先定義兩個(gè)集合：
up_right(k) ： 節(jié)點(diǎn)k所有的父節(jié)點(diǎn)，且節(jié)點(diǎn)k在它們的左子樹下。
up_left(k) ： 節(jié)點(diǎn)k所有的父節(jié)點(diǎn)，且節(jié)點(diǎn)k在它們的右子樹下。
1 更新數(shù)據(jù)x，查詢區(qū)間[1,y]。
顯然，更新葉子x，要找出葉子x在哪些節(jié)點(diǎn)的左子樹下。因而節(jié)點(diǎn)k、所有的up_right(k)
都要更新。
查詢[1, y]，實(shí)際上就是把該區(qū)間拆分成一系列小區(qū)間，并找出統(tǒng)計(jì)這些區(qū)間的節(jié)點(diǎn)。可以通過找出y在哪些節(jié)點(diǎn)的右子樹下，這些節(jié)點(diǎn)恰好不重復(fù)的統(tǒng)計(jì)了區(qū)間[1, y-1]。因而要訪問節(jié)點(diǎn)y、所有的up_left(y)。
2 更新區(qū)間[1,y]，查詢數(shù)據(jù)x
這和前面的操作恰好相反。與前面的最大不同之處在于：節(jié)點(diǎn)保存的不再是其葉子總個(gè)數(shù)這些信息，而是該區(qū)間的所有葉子都改變了多少。也就是說：每個(gè)葉子的信息，分散到了所有對(duì)它統(tǒng)計(jì)的節(jié)點(diǎn)上。因此操作和前面相似：
更新[1,y]時(shí)，更新節(jié)點(diǎn)y、所有up_left(y)。
查詢x時(shí)， 訪問x、所有up_right(x)。
前面的樹狀數(shù)組，只對(duì)左子樹信息進(jìn)行統(tǒng)計(jì)，如果從后往前讀數(shù)據(jù)初始化樹狀數(shù)組，則變成只對(duì)右子樹信息進(jìn)行統(tǒng)計(jì)，這時(shí)更新和查詢操作，剛好和前面的相反。
一般情況下，樹狀數(shù)組比點(diǎn)樹省空間，對(duì)區(qū)間[1, M]只要M+1空間，查詢更新時(shí)定位節(jié)點(diǎn)比較快，定位父節(jié)點(diǎn)和左右孩子相對(duì)麻煩點(diǎn)（不過，一般也不用到。從上往下查找，可參考下面代碼中的erease_nth函數(shù)（刪除第n小的數(shù)））。
下面是使用樹狀數(shù)組的實(shí)現(xiàn)代碼（求逆序數(shù)和模擬約瑟夫環(huán)問題）：
樹狀數(shù)組
//www.cnblogs.com/flyinghearts
#include<cstdio>
#include<cstring>
#include<cassert>
template<int N> struct Round2k
{ enum { down = Round2k<N / 2u>::down * 2}; };
template<> struct Round2k<1> { enum { down = 1}; };
template <int Total, typename T = int> //區(qū)間[1, Total]
class BIT {
enum { Min2k = Round2k<Total>::down};
T info[Total + 1];
T sz; //可以用info[0]儲(chǔ)存總大小
public:
BIT() { clear(); }
void clear() { memset(this, 0, sizeof(*this));}
int size() { return sz; }
int lowbit(int idx) { return idx & -idx;}
//尋找最近的父節(jié)點(diǎn)，left_up/right_up 分別使得idx在其右/左子樹下
void left_up(int& idx) { idx -= lowbit(idx); }
void right_up(int& idx) { idx += lowbit(idx); }
void update(int idx ,const int val = 1) { //葉子idx 改變val個(gè)
assert(idx > 0);
sz += val;
for (; idx <= Total; right_up(idx)) info[idx] += val;
}
void init(int arr[], int n) { // arr[i]為葉子i+1的個(gè)數(shù)
assert(n <= Total);
sz = n;
// for (int i = 0; i < n; ) {
// info[i + 1] = arr[i];
// if (++i >= n) break;
// info[i + 1] = arr[i];
// ++i;
// for (int j = 1; j < lowbit(i); j *= 2u) info[i] += info[i - j];
// }
for (int i = 0; i < n; ) {
info[i + 1] = arr[i];
if (++i >= n) break;
int sum = arr[i];
int pr = ++i;
left_up(pr);
for (int j = i - 1; j > pr; left_up(j)) sum += info[j];
info[i] = sum;
}
}
int count(int idx) { //[1,idx] - [1, idx-1]
assert(idx > 0);
int sum = info[idx];
// int pr = idx; //int pr = idx - lowbit(idx);
// left_up(pr);
// for (--idx; idx > pr; left_up(idx)) sum -= info[idx]; //
// return sum;
for (int j = 1; j < lowbit(idx); j *= 2u) sum -= info[idx - j];
return sum;
}
int lteq(int idx) { //小等于
assert(idx >= 1 && idx <= Total);
int sum = 0;
for (; idx > 0; left_up(idx)) sum += info[idx];
return sum;
}
int gt(int idx) { return sz - lteq(idx); } //大于
int operator[](int n) { return erase_nth(n, 0); } //第n小
int erase_nth(int n, const bool erase_flag = true) //刪除第n小的數(shù)
{
assert(n >=1 && n <= sz);
sz -= erase_flag;
int idx = Min2k; //從上往下搜索，先定位根節(jié)點(diǎn)
for (int k = idx / 2u; k > 0; k /= 2u) {
int t = info[idx];
if (n <= info[idx]) { info[idx] -= erase_flag; idx -= k;} //進(jìn)入左子樹
else {
n -= t;
if (Total != Min2k && Total != Min2k - 1) //若不是完全二叉樹
while (idx + k > Total) k /= 2u; //則必須計(jì)算右孩子的編號(hào)
idx += k; //進(jìn)入右子樹
}
}
assert(idx % 2u); //最底層節(jié)點(diǎn)m一定是奇數(shù)，有兩個(gè)葉子m，m+1
if (n > info[idx]) return idx + 1; //節(jié)點(diǎn)m+1前面已經(jīng)更新過
info[idx] -= erase_flag;
return idx;
}
void show()
{
for (int i = 1; i <= Total; ++i)
if (count(i)) printf("%2d ", i);
printf("\n");
}
};
void ring() //約瑟夫環(huán)
{
const int N = 17; //N個(gè)人編號(hào)：1,2, N
const int M = 7; //報(bào)數(shù)：1到M，報(bào)到M的出列
printf(" N: %d M: %d\n", N, M);
BIT<N> pt;
// for (int i = 0; i < N; ++i) pt.update(i + 1);
int arr[N];
for (int i = 0; i < N; ++i) arr[i] = 1;
pt.init(arr, N);
for (int j = N, k = 0; j >= 1; --j) {
k = (k + M-1) % j;
int t = pt.erase_nth(k + 1);
printf(" turn: %2d out: %2d rest: ", N - j, t);
pt.show();
}
printf(" \n\n");
}
int ra(int arr[], int len) //求逆序數(shù)-直接搜索
{
int sum = 0;
for (int i = 0; i < len - 1; ++i)
for (int j = i + 1; j < len; ++j)
if (arr[i] > arr[j]) ++sum;
return sum;
}
template<int N>
int rb(int arr[], int len) //求逆序數(shù)-使用樹狀數(shù)組
{
BIT<N> pt;
int sum = 0;
for (int i = 0; i < len; ++i) {
pt.update(arr[i] + 1);
sum += pt.gt(arr[i] + 1);
}
return sum;
}
int main()
{
int arr[] = { 4,3,2,1,0,5, 1,3,0,2};
const int N = sizeof(arr) / sizeof(arr[0]);
printf("%d %d\n\n", ra(arr, N), rb<6>(arr, N));
ring();
}
作者： flyinghearts
出處： http://www.cnblogs.com/flyinghearts/
本文采用知識(shí)共享署名-非商業(yè)性使用-相同方式共享 2.5 中國(guó)大陸許可協(xié)議進(jìn)行許可，歡迎轉(zhuǎn)載，但未經(jīng)作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接，否則保留追究法律責(zé)任的權(quán)利。