python實現fenwick tree芬威克樹算法案例

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

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

fenwick tree芬威克樹算法介紹

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

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

基本概念

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

原理

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

主要操作

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

實現

Fenwick Tree的實現通常包括以下幾個部分：

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

示例

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

注意事項

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

fenwick tree芬威克樹算法python實現樣例

Fenwick Tree（也稱為Binary Indexed Tree）是一種用于高效計算前綴和（Prefix Sum）的數據結構，可以在O(log 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類的構造函數接受一個整數參數n，表示Fenwick Tree的大小。