Fenwick Tree
(data-structure/fenwick.hpp)

• View this file on GitHub
• Last update: 2023-07-25 00:50:50+07:00
• Include: #include "data-structure/fenwick.hpp"

Required by

• Fenwick Tree 2D (data-structure/fenwick2d.hpp)

Verified with

• data-structure/test/Point_Add_Range_Sum.test.cpp
• data-structure/test/The_Maximum_Number_of_Overlaps.test.cpp

Code

template <typename T>
struct fenwick {
  fenwick(int n) : n(n), f(n + 1) {}

  // a[u] += val
  void add(int u, T val) {
    assert(0 <= u && u < n);
    ++u;
    while (u <= n) f[u] += val, u += u & -u;
  }

  // return the sum of [0, u)
  T sum(int u) const {
    assert(0 <= u && u <= n);
    T res = 0;
    while (u) res += f[u], u -= u & -u;
    return res;
  }

  // return the sum of [l, r)
  T sum(int l, int r) const {
    assert(0 <= l && l <= r && r <= n);
    if (l == r) return 0;
    return sum(r) - sum(l);
  }

  void reset() { fill(f.begin(), f.end(), T(0)); }

  int n;
  vector<T> f;
};

#line 1 "data-structure/fenwick.hpp"
template <typename T>
struct fenwick {
  fenwick(int n) : n(n), f(n + 1) {}

  // a[u] += val
  void add(int u, T val) {
    assert(0 <= u && u < n);
    ++u;
    while (u <= n) f[u] += val, u += u & -u;
  }

  // return the sum of [0, u)
  T sum(int u) const {
    assert(0 <= u && u <= n);
    T res = 0;
    while (u) res += f[u], u -= u & -u;
    return res;
  }

  // return the sum of [l, r)
  T sum(int l, int r) const {
    assert(0 <= l && l <= r && r <= n);
    if (l == r) return 0;
    return sum(r) - sum(l);
  }

  void reset() { fill(f.begin(), f.end(), T(0)); }

  int n;
  vector<T> f;
};

Back to top page