深入理解FenwickTree

小蓝 • 2024-12-12 12:53 • 编程

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的基本用法。

原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/242885.html