深入理解FenwickTree

FenwickTree，也稱作Binary Index Tree，是一種數據結構，廣泛應用於區間查詢和單點更新的場景中。在實際應用中，FenwickTree常用於求和問題，其時間複雜度為O(log n)。本文將從多個方面對FenwickTree做詳細講解，並提供代碼示例供讀者參考。

一、創建FenwickTree的步驟

1. 創建FenwickTree數組：FenwickTree實際上是一個由數組構成的二叉樹。數組第i個元素保存的是原數組中從第i個元素到第i-2千的元素和。

template
class FenwickTree {
public:
    FenwickTree(int n): sums_(n + 1) {}
    void update(int i, T delta) {
        while (i  0) {
            sum += sums_[i];
            i -= lowbit(i);
        }
        return sum;
    }
private:
    static inline int lowbit(int x) { return x & (-x); }
    vector sums_;
};

2. 初始化FenwickTree數組：在將原始數組的值更新到FenwickTree數組之前，需要對所有元素進行初始化。可以通過對原數組的所有元素進行遍歷，將每個元素的值傳遞給update函數進行初始化。

for (int i = 0; i < n; ++i)
    tree.update(i + 1, nums[i]);

二、求解前綴和

查詢區間[L, R]的和可以轉化為求解前綴和sum[L – 1]和sum[R]的差值。因此，可以通過query函數分別查詢sum[L – 1]和sum[R]的值，再計算出[L, R]區間內元素之和的值。query函數的實現代碼如下。

T query(int i) const {
    T sum = 0;
    while (i > 0) {
        sum += sums_[i];
        i -= lowbit(i);
    }
    return sum;
}

三、更新元素

更新元素通常是指將原始數組中下標為i的元素更新為v。因為FenwickTree用來維護前綴和，所以FenwickTree的更新操作也需要對應的是前綴和的更新。因此，更新值是v和原始值的差值delta。update函數的實現代碼如下。

void update(int i, T delta) {
    while (i < sums_.size()) {
        sums_[i] += delta;
        i += lowbit(i);
    }
}

四、FenwickTree vs. 線段樹

FenwickTree和線段樹是兩種常見的數據結構，它們在求解區間查詢和單點更新問題上表現優異。不過，兩者的實現方法和應用場景有所不同。下面對兩者的異同點進行總結。

相同點：

1. 兩者都能夠在O(log n)時間內進行查詢和更新。

不同點：

1. 線段樹是完全二叉樹；FenwickTree是二叉樹，每個節點的左右子節點都是樹上前一個節點和該節點加上其lowbit獲得。

2. 線段樹更加靈活，在解決更加複雜的問題時具有更強的適用性。但是，它所需的時間和空間要比FenwickTree更多。

3. FenwickTree比線段樹使用更少的空間，但是其實現方法需要注意一些細節。

五、總結

在區間查詢和單點更新問題中，FenwickTree是一種高效的數據結構。本文詳細介紹了FenwickTree的實現方法，包括創建FenwickTree的步驟、求解前綴和和更新元素以及與線段樹的比較等方面。希望本文能夠幫助讀者快速了解並掌握FenwickTree的基本用法。