樹(shù)狀數(shù)組的緣起

相信大家對(duì)數(shù)組這一基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)都有所了解， 本質(zhì)上數(shù)組在內(nèi)存中是一段連續(xù)的地址, 我們可以通過(guò)地址偏移來(lái)訪問(wèn)元素，這個(gè)操作在計(jì)算機(jī)中效率是非常高的, 時(shí)間復(fù)雜度為O(1), 但是如果我們要對(duì)一個(gè)數(shù)組求和的話， 時(shí)間復(fù)雜度為O(n)。

想要優(yōu)化數(shù)組求和的復(fù)雜度的話，你可能會(huì)想到會(huì)求前綴和數(shù)組來(lái)實(shí)現(xiàn)O(1)的效果, 但是如果要修改數(shù)組里面的值, 就要修改前綴和里面的值, 時(shí)間復(fù)雜度為O(n)。

于是就有了兩種極端, 那么有沒(méi)有一種既能快速查詢也能快速求和的數(shù)據(jù)結(jié)構(gòu)呢?

什么是樹(shù)狀數(shù)組(Fenwick Tree)？

說(shuō)白了本質(zhì)上就是用數(shù)組去模擬一顆樹(shù),? 更新和求和的復(fù)雜度都為O(logn) (這個(gè)后面會(huì)證明)

要理解用數(shù)組是怎么去構(gòu)建一顆樹(shù), 實(shí)際上很簡(jiǎn)單, 我們先了解一下關(guān)于二進(jìn)制的性質(zhì)

我們知道對(duì)于任何正整數(shù)x,?都可以將它分解為二進(jìn)制位權(quán)展開(kāi)的形式:

樹(shù)狀數(shù)組本質(zhì)上就是通過(guò)二進(jìn)制的位權(quán)展開(kāi)來(lái)對(duì)求和進(jìn)行優(yōu)化的, 如果我們能把一個(gè)數(shù)組分為不同的區(qū)間, 并從小區(qū)間開(kāi)始求和, 在利用保存過(guò)的小區(qū)間的值去推算出大區(qū)間的值。從此優(yōu)化了求和的效率. 例如我們要對(duì)一個(gè)長(zhǎng)度n = 256的數(shù)組求和, 如果用一個(gè)for循環(huán)我們要算256次, 但利用樹(shù)狀數(shù)組只需要計(jì)算8次。

下面給出幾個(gè)例子, tree代表樹(shù)狀數(shù)組, a代表原數(shù)組:

• tree[1] = A[1];

• tree[2] = A[1] + A[2];

• tree[3] = A[3];

• tree[4] = tree[2]?+ A[3] + A[4]

  ? ? ? ? ? ?= A[1] + A[2] + A[3] + A[4];

• tree[5] = A[5];

• tree[6] = A[5] + A[6];

• tree[7] = A[7];

• tree[8] =? tree[4] + tree[6] + A[7] + A[8]?

  ? ? ? ? ? =A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] + A[8];

于是我們可以發(fā)現(xiàn)樹(shù)狀數(shù)組的幾個(gè)性質(zhì):

tree[i] = A[i - 2^k+1] + A[i - 2^k+2] + ... + A[i]

其中 k 是二進(jìn)制中最后一個(gè)1的值。

如何理解呢? 通過(guò)繼續(xù)觀察我們可以發(fā)現(xiàn)當(dāng) i 為奇數(shù)時(shí), tree[i] = A[i] 總是成立的, 比如上面的 tree[3] = A[3], tree[5] =?A[5], tree[7] = A[7]。

如何證明這一性質(zhì)呢? 下面我們來(lái)證明: 當(dāng) n 是奇數(shù)時(shí), 當(dāng)且僅當(dāng) n 的二進(jìn)制最后一位為 1 .

假設(shè) n = 2 * m + 1, 因?yàn)?n % 2 = 1，所以當(dāng)我們?cè)趯?n 轉(zhuǎn)換為二進(jìn)制的過(guò)程中 (不斷 / 2 取余數(shù)) 最后一位必定為 1， 證畢。

對(duì)稱地,? 當(dāng) n 為偶數(shù)時(shí), 最后一位不為 0。 這就是為什么 n 為偶數(shù)時(shí) tree[n] 都可以分解為 至少兩個(gè)區(qū)間的和了。 例如 2 (10), 4 (100), 6 (110)...

那么我們就理解了 k 的含義:?二進(jìn)制中最后一個(gè)1的值。

如何實(shí)現(xiàn)樹(shù)狀數(shù)組

分析了樹(shù)狀數(shù)組的性質(zhì)后, 我們就可以更任意地實(shí)現(xiàn)樹(shù)狀數(shù)組了。

首先我們定義函數(shù) k = lowbit(i) 來(lái)求出 i 的進(jìn)制中最后一個(gè)1的值并賦值給 k

我們可以證明以下性質(zhì):?當(dāng)x為0時(shí)結(jié)果為0；x為奇數(shù)時(shí)，結(jié)果為1；x為偶數(shù)時(shí)，結(jié)果為x中2的最大次方的因子

這里利用了負(fù)數(shù)的補(bǔ)碼存儲(chǔ)，當(dāng)x為0時(shí), 結(jié)果很顯然是0, 當(dāng)x為奇數(shù)時(shí), 因?yàn)?strong>補(bǔ)碼 = 反碼 + 1,

那么 -x 的最后一位必然是 1, 于是x 和 -x 除了最后一位都為 1 外其他為都相反, 于是我們按位與后的結(jié)果為 1

當(dāng) x 為偶數(shù)的時(shí)候, 我們可以通過(guò)討論 x 是否為 2 次冪來(lái)證明這個(gè)函數(shù)的正確性, 思路大致都一樣，這里就不詳細(xì)寫(xiě)了。。。

于是我們可以構(gòu)建出我們的求和函數(shù)了， 只要 i 不為0，我們就一直讓它減去 lowbit(i), 相當(dāng)于上述的整數(shù)分解為二進(jìn)制的過(guò)程:

如何實(shí)現(xiàn)更新樹(shù)狀數(shù)組里面的元素呢? 我們考慮從子節(jié)點(diǎn)向父節(jié)點(diǎn)更新(向上更新)我們也可以快速地寫(xiě)出代碼了:

證明樹(shù)狀數(shù)組的時(shí)間復(fù)雜度

最后再模仿<<算法導(dǎo)論>>里的套路, 證明一下時(shí)間復(fù)雜度吧!?

已知我們把數(shù)組分解成了最多l(xiāng)ogx個(gè)區(qū)間, 那么我們只需對(duì)每個(gè)區(qū)間求和就可以得到整個(gè)數(shù)組的和, 如果有n個(gè)元素, 那么很容易推出求和的時(shí)間復(fù)雜度為O(logn)。

下面我們來(lái)證明更新時(shí)的復(fù)雜度為 O(logn), 由于查詢是從子節(jié)點(diǎn)向上更新的, 那么要爬到 n 也需要 log (n - i) 次, 那么時(shí)間復(fù)雜度也是 O(logn)級(jí)別的。

總結(jié)

本蒟蒻學(xué)這個(gè)算法時(shí)也很蒙蔽，主要當(dāng)時(shí)二進(jìn)制的思想還理解得不夠深,? 實(shí)際上這個(gè)算法的優(yōu)雅之處在于用二進(jìn)制的將一個(gè)數(shù)組拆分來(lái)進(jìn)行優(yōu)化, 而且代碼比起線段樹(shù)也很簡(jiǎn)潔, 據(jù)說(shuō)還有大佬能用樹(shù)狀數(shù)組實(shí)現(xiàn)一顆平衡樹(shù)。 這種用倍增的思想去降低時(shí)間復(fù)雜度的技巧還是值得我們?nèi)W(xué)習(xí)的。?

最后在把代碼獻(xiàn)上吧: