快捷導(dǎo)航

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

更新時間：2024年10月21日 09:42:18 作者：luthane

芬威克樹,又稱為二叉索引樹或樹狀數(shù)組,是一種高效的數(shù)據(jù)結(jié)構(gòu),由Peter M. Fenwick于1994年提出,主要用于計算數(shù)組的前綴和以及支持對數(shù)時間復(fù)雜度的元素更新,通過維護一個特定的數(shù)組,利用整數(shù)的二進制特性進行區(qū)間和存儲

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主要用于高效地計算數(shù)字序列（數(shù)組）的前綴和，同時支持對數(shù)時間復(fù)雜度的元素更新操作。

基本概念

Fenwick Tree通過維護一個數(shù)組來記錄原數(shù)組在不同區(qū)間的和，以便在O(log n)的時間復(fù)雜度內(nèi)回答前綴和查詢和單點更新的問題。
與傳統(tǒng)的前綴和數(shù)組相比，F(xiàn)enwick Tree在處理頻繁的元素更新時更加高效，因為它不需要重新構(gòu)建整個前綴和數(shù)組。

原理

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

主要操作

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

實現(xiàn)

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

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

示例

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

注意事項

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

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

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

下面是一個實現(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

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

    # 計算區(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ù)接受一個整數(shù)參數(shù)n，表示Fenwick Tree的大小。