ds/Fenwick.h

• View this file on GitHub
• Last update: 2025-12-09 07:33:19+07:00

Verified with

• tests/Point_Add_Range_Sum.test.cpp
• tests/Vertex_Add_Path_Sum.test.cpp

Code

// for 2d fenwick just add a for
template <class T>
struct Fenwick {  // 1-indexed
  int n;
  vector<T> t;
  Fenwick(int n) : n(n), t(n + 1, T(0)) {}
  void add(int p, T v) {
    while (p <= n) t[p] += v, p += (p & -p);
  }
  T sum(int p) {
    T res = 0;
    while (p) res += t[p], p -= (p & -p);
    return res;
  }
  // [l, r)
  T sum(int l, int r) {
    if (l > r) return T(0);
    return sum(r) - sum(l - 1);
  }
};

#line 1 "ds/Fenwick.h"
// for 2d fenwick just add a for
template <class T>
struct Fenwick {  // 1-indexed
  int n;
  vector<T> t;
  Fenwick(int n) : n(n), t(n + 1, T(0)) {}
  void add(int p, T v) {
    while (p <= n) t[p] += v, p += (p & -p);
  }
  T sum(int p) {
    T res = 0;
    while (p) res += t[p], p -= (p & -p);
    return res;
  }
  // [l, r)
  T sum(int l, int r) {
    if (l > r) return T(0);
    return sum(r) - sum(l - 1);
  }
};

Back to top page