fenwick tree芬威克樹算法介紹

Fenwick Tree，也被稱為Binary Indexed Tree（二叉索引樹）或樹狀數(shù)組，是由Peter M. Fenwick在1994年以“A New Data Structure for Cumulative Frequency Tables”為題首次介紹的一種數(shù)據(jù)結(jié)構(gòu)。

Fenwick Tree主要用于高效地計(jì)算數(shù)字序列（數(shù)組）的前綴和，同時(shí)支持對(duì)數(shù)時(shí)間復(fù)雜度的元素更新操作。

基本概念

• Fenwick Tree通過(guò)維護(hù)一個(gè)數(shù)組來(lái)記錄原數(shù)組在不同區(qū)間的和，以便在O(log n)的時(shí)間復(fù)雜度內(nèi)回答前綴和查詢和單點(diǎn)更新的問(wèn)題。
• 與傳統(tǒng)的前綴和數(shù)組相比，F(xiàn)enwick Tree在處理頻繁的元素更新時(shí)更加高效，因?yàn)樗恍枰匦聵?gòu)建整個(gè)前綴和數(shù)組。

原理

• Fenwick Tree利用整數(shù)的二進(jìn)制表示特性，將每個(gè)元素與多個(gè)區(qū)間相關(guān)聯(lián)，并將這些區(qū)間的和存儲(chǔ)在Fenwick Tree的數(shù)組中。
• 每個(gè)索引i在Fenwick Tree中對(duì)應(yīng)的節(jié)點(diǎn)存儲(chǔ)的是從i - lowbit(i) + 1到i（包含）的區(qū)間內(nèi)所有元素的和，其中l(wèi)owbit(i)是i在二進(jìn)制表示下最低位的1所對(duì)應(yīng)的值。

主要操作

• 單點(diǎn)更新：當(dāng)需要更新原數(shù)組中的某個(gè)元素時(shí)，F(xiàn)enwick Tree通過(guò)修改該元素在Fenwick Tree中對(duì)應(yīng)節(jié)點(diǎn)及其所有祖先節(jié)點(diǎn)的值來(lái)反映這一變化，這一過(guò)程的時(shí)間復(fù)雜度為O(log n)。
• 前綴和查詢：對(duì)于給定的索引x，F(xiàn)enwick Tree通過(guò)累加從x到根節(jié)點(diǎn)路徑上所有節(jié)點(diǎn)的值來(lái)計(jì)算從數(shù)組開頭到索引x（包含）的元素和，這一過(guò)程的時(shí)間復(fù)雜度同樣為O(log n)。

實(shí)現(xiàn)

Fenwick Tree的實(shí)現(xiàn)通常包括以下幾個(gè)部分：

• 初始化：創(chuàng)建一個(gè)與原始數(shù)組等長(zhǎng)的Fenwick Tree數(shù)組，并將所有元素初始化為0。
• 單點(diǎn)更新：通過(guò)不斷累加index + lowbit(index)的方式，更新Fenwick Tree中對(duì)應(yīng)節(jié)點(diǎn)的值。
• 前綴和查詢：通過(guò)不斷減去index - lowbit(index)的方式，累加Fenwick Tree中對(duì)應(yīng)節(jié)點(diǎn)的值，直到index為0。

示例

• 假設(shè)有一個(gè)數(shù)組a = [1, 2, 3, 4, 5]，我們可以構(gòu)建一個(gè)Fenwick Tree來(lái)高效地計(jì)算前綴和。
• 例如，要計(jì)算前綴和a[0] + a[1] + a[2]，我們只需要在Fenwick Tree中進(jìn)行幾次簡(jiǎn)單的查找和累加操作即可。

注意事項(xiàng)

• Fenwick Tree只能高效地處理前綴和查詢和單點(diǎn)更新操作，對(duì)于其他類型的區(qū)間查詢和更新操作可能不適用。
• 在實(shí)現(xiàn)Fenwick Tree時(shí)，需要注意數(shù)組索引的偏移（通常從1開始而不是從0開始），以簡(jiǎn)化操作并避免越界問(wèn)題。

fenwick tree芬威克樹算法python實(shí)現(xiàn)樣例

Fenwick Tree（也稱為Binary Indexed Tree）是一種用于高效計(jì)算前綴和（Prefix Sum）的數(shù)據(jù)結(jié)構(gòu)，可以在O(log n)時(shí)間內(nèi)進(jìn)行插入、查詢和更新操作。

下面是一個(gè)實(shí)現(xiàn)Fenwick Tree算法的Python代碼示例：

class FenwickTree:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    # 更新操作：將索引i位置的元素增加delta
    def update(self, i, delta):
        while i <= self.size:
            self.tree[i] += delta
            i += i & -i

    # 查詢操作：計(jì)算前i個(gè)元素的和
    def query(self, i):
        res = 0
        while i > 0:
            res += self.tree[i]
            i -= i & -i
        return res

    # 計(jì)算區(qū)間[i, j]的和
    def range_query(self, i, j):
        return self.query(j) - self.query(i-1)

使用示例：

fenwick_tree = FenwickTree(10)
fenwick_tree.update(1, 2)
fenwick_tree.update(3, -1)
fenwick_tree.update(5, 5)

print(fenwick_tree.range_query(1, 5))  # 輸出：6
print(fenwick_tree.range_query(3, 7))  # 輸出：4

在上面的代碼中，FenwickTree類的構(gòu)造函數(shù)接受一個(gè)整數(shù)參數(shù)n，表示Fenwick Tree的大小。

• update方法用于更新Fenwick Tree中的某個(gè)元素
• query方法用于計(jì)算前i個(gè)元素的和
• range_query方法用于計(jì)算區(qū)間[i, j]的和

在使用Fenwick Tree的時(shí)候，可以根據(jù)實(shí)際需求進(jìn)行適當(dāng)?shù)男薷摹?/p>

例如：

• 可以將update方法修改為將索引i位置的元素設(shè)置為delta，而不是增加delta。
• 高級(jí)應(yīng)用還包括計(jì)算逆序?qū)€(gè)數(shù)、計(jì)算逆序?qū)Φ暮偷鹊取?/li>

總結(jié)

以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

最新評(píng)論