Fenwick Tree is mainly designed for solving the single point update range sum problems. e.g. what’s the sum between i-th and j-th element while the values of the elements are mutable.

Init the tree (include building all prefix sums) takes O(nlogn)

Update the value of an element takes O(logn)

Query the range sum takes O(logn)

Space complexity: O(n)

class FenwickTree {
 public:
  FenwickTree(int n) : sums_(n + 1, 0) {}

  void update(int i, int delta) {
    while (i < sums_.size()) {
      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_;
};

Relative problems

By guozetang            Updated: 2020-09-19 13:02:30

results matching ""

    No results matching ""