树状数组 Fenwick Tree

Fenwick Tree，Binary Indexed Tree

树状数组，又叫二元索引树，或者，Fenwick树，是Fenwick发明的一种数据结构。这种数据结构通常用来计算数组的前缀和，区间和。

这种数据结构更新节点的时间复杂度是 $\mathcal{O}(log_n)$，计算任意前缀和的时间复杂度也是 $\mathcal{O}(log_n)$，空间复杂度依旧为$\mathcal{O}(n)$。

详细的介绍，原理，过程等，可以看一看花花的这个视频。

一种 c++ 实现如下。

class FenWickTree {
   public:
    FenWickTree(int n): sums_(n + 1) {};

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

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

   private:
    static inline int lowbit(int x) { return x & (-x); }
    vector<int> sums_;
  };

树状数组 Fenwick Tree

相关文章：