Bitree 2D.cpp

/*8<{=========~ BEGIN BIT TREE 2D ~===========>8*/
/*8<
  @Title:
    Bitree 2D

  @Description:

    Given a 2D array you can increment an
    arbitrary position, and also query
    the subsum of a subgrid

  @Time:

    Update and query in $O(log{N^2})$

 >8*/

struct Bit2d {
  int n;
  vll2d bit;
  Bit2d(int ni) : n(ni), bit(n + 1, vll(n + 1)) {}
  Bit2d(int ni, vll2d &xs)
      : n(ni), bit(n + 1, vll(n + 1)) {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        update(i, j, xs[i][j]);
      }
    }
  }
  void update(int x, int y, ll val) {
    for (; x <= n; x += (x & (-x))) {
      for (int i = y; i <= n; i += (i & (-i))) {
        bit[x][i] += val;
      }
    }
  }
  ll sum(int x, int y) {
    ll ans = 0;

    for (int i = x; i; i -= (i & (-i))) {
      for (int j = y; j; j -= (j & (-j))) {
        ans += bit[i][j];
      }
    }
    return ans;
  }
  ll query(int x1, int y1, int x2, int y2) {
    return sum(x2, y2) - sum(x2, y1 - 1) -
           sum(x1 - 1, y2) + sum(x1 - 1, y1 - 1);
  }
};

/*8<========================================}>8*/