在 四元环问题、树状数组以及一些经典题的总结 里，总结了许多种树状数组的基本写法，但函数式的模板看起来总是不那么简洁和美观，于是参考了 Tourist 的模板，结合旧版，总结了三种（普通一维，维护最值、二维）树状数组的面向对象写法。

如果有错误请大家在评论区指出，谢谢。

普通树状数组

template <typename T>
class Fenwick {
 public:
  vector<T> fenw;
  int n;
  Fenwick(int _n) : n(_n) {
    fenw.resize(n);
  }
  // change value at x to v
  inline void add(int x, T v) {
    assert(x >= 0 && x < n);
    while (x < n) {
      fenw[x] += v;
      x |= (x + 1);
    }
  }
  inline T get(int x) {
    T res{};
    while (x >= 0) {
      res += fenw[x];
      x = (x & (x + 1)) - 1;
    }
    return res;
  }
  // ask for [l, r]
  inline T get(int l, int r) {
    assert(l >= 0 && l < n && r >= 0 && r < n);
    T res = get(r);
    if (l - 1 >= 0) {
      res -= get(l - 1);
    }
    return res;
  }
};
// struct node {
//   int a = ...; // don't forget to set default value
//   inline void operator += (node &other) {
//     ...
//   }
// };

维护最值树状数组

这个模板挺好用的，在大多数情况可以代替 RMQ ，而且功能更加强大，支持了单点修改。

// usage:
//   auto fun = [&](int i, int j) { return min(i, j); };
//   Fenwick<int, decltype(fun)> fen(a, fun);
// or:
//   Fenwick<int> fen(a, [&](int i, int j) { return min(i, j); });
template <typename T, class F = function<T(const T&, const T&)>>
class Fenwick {
 public:
  int n;
  vector<T> val, fenw;
  F func;
  Fenwick (const vector<T>& a, const F& f) : func(f) {
    n = static_cast<int>(a.size());
    val.resize(n);
    fenw.resize(n);
    for (int i = 1; i <= n; i++) {
      val[i - 1] = fenw[i - 1] = a[i - 1];
      int len = lowbit(i);
      for (int j = 1; j < len; j <<= 1) {
        fenw[i - 1] = func(fenw[i - 1], fenw[i - j - 1]);
      }
    }
  }
  // change value at k to v
  // k is [0, n)
  inline void modify(int k, T v) {
    assert(k >= 0 && k < n);
    val[k] = v;
    for (int i = k + 1; i <= n; i += lowbit(i)) {
      fenw[i - 1] = val[i - 1];
      int len = lowbit(i);
      for (int j = 1; j < len; j <<= 1) {
        fenw[i - 1] = func(fenw[i - 1], fenw[i - j - 1]);
      }
    }
  }
  // l and r are [0, n)
  // ask for [l, r]
  inline T query(int l, int r) {
    assert(l >= 0 && l < n);
    assert(r >= 0 && r < n);
    ++l, ++r;
    T res = val[r - 1];
    while (true) {
      res = func(res, val[r - 1]);
      if (l == r) break;
      for (--r; r - lowbit(r) >= l; r -= lowbit(r)) {
        res = func(res, fenw[r - 1]);
      }
    }
    return res;
  }
};

二维树状数组

// 2D Fenwick
template <typename T>
class Fenwick {
 public:
  vector<vector<T> > fenw;
  int n, m;
  Fenwick(int _n, int _m) : n(_n), m(_m) {
    fenw.resize(n + 1);
    for (int i = 0; i < n; i++) {
      fenw[i].resize(m);
    }
  }
  // Change value at (x, y) to v
  inline void add(int x, int y, T v) {
    assert(x >= 0 && x < n && y >= 0 && y < m);
    for (int i = x + 1; i <= n; i += lowbit(i)) {
      for (int j = y + 1; j <= m; j += lowbit(j)) {
        fenw[i - 1][j - 1] += v;
      }
    }
  }
  inline T get(int x, int y) {
    assert(x >= 0 && x < n && y >= 0 && y < m);
    T res{};
    for (int i = x + 1; i >= 1; i -= lowbit(i)) {
      for (int j = y + 1; j >= 1; j -= lowbit(j)) {
        res += fenw[i - 1][j - 1];
      }
    }
    return res;
  }
  // ask for [x1, x2] and [y1, y2]
  inline T get(int x1, int y1, int x2, int y2) {
    assert (x1 <= x2 && y1 <= y1);
    assert(x1 >= 0 && x1 < n && x2 >= 0 && x2 < n);
    assert(y1 >= 0 && y1 < m && y2 >= 0 && y2 < m);
    T res = get(x2, y2);
    if (x1 - 1 >= 0) {
      res -= get(x1 - 1, y2);
    }
    if (y1 - 1 >= 0) {
      res -= get(x2, y1 - 1);
    }
    if (x1 - 1 >= 0 && y1 - 1 >= 0) {
      res += get(x1 - 1, y1 - 1);
    }
    return res;
  }
};
// struct node {
//   int a = ...; // don't forget to set default value
//   inline void operator += (node &other) {
//     ...
//   }
// };