Fenwick2D

template <typename T>
struct Fenwick2D {
  int n, m;
  std::vector<std::vector<T>> a;

  Fenwick2D(int n, int m) : n(n), m(m) {
    a.assign(n, std::vector<T>(m));
  }

  template <typename M>
  Fenwick2D(const std::vector<std::vector<M>>& v) {
    n = int(v.size());
    m = (n == 0 ? 0 : int(v[0].size()));
    a.assign(n, std::vector<T>(m));
    for (int i = 0; i < n; ++i) {
      std::copy(v[i].begin(), v[i].end(), a[i].begin());
    }
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        if (int k = i | (i + 1); k < n) {
          a[k][j] += a[i][j];
        }
      }
    }
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        if (int k = j | (j + 1); k < m) {
          a[i][k] += a[i][j];
        }
      }
    }
  }

  void modify(int x, int y, T v) {
    for (int i = x; i < n; i |= i + 1) {
      for (int j = y; j < m; j |= j + 1) {
        a[i][j] += v;
      }
    }
  }

  [[nodiscard]] T get(int x, int y) const {
    assert(-1 <= x && x < n && -1 <= y && y < m);
    T res {};
    for (int i = x; i >= 0; i = (i & (i + 1)) - 1) {
      for (int j = y; j >= 0; j = (j & (j + 1)) - 1) {
        res += a[i][j];
      }
    }
    return res;
  }

  [[nodiscard]] T rangeSum(int x0, int y0, int x1, int y1) const {
    return get(x1 - 1, y1 - 1) - get(x1 - 1, y0 - 1) - get(x0 - 1, y1 - 1) + get(x0 - 1, y0 - 1);
  }
};