2次元(二次元)BITクラス

参考

Code

// 実装参照 http://hos.ac/slides/20140319_bit.pdf
// 注意
// 1-indexedです
struct BIT2D{
  VV bit;
  ll W,H;
  // widthが先なので注意
  void resize(ll w, ll h){
    W = w;
    H = h;
    // bit[x][y]の順に確保することに注意
    bit.resize(W+10, VI(H+10));
  }
  // x, yの順
  void add(ll a, ll b, ll w) {
    if(a==0 or b==0){
      debug("[warning] it is 1-indexed"); exit(0);
    }
    for (ll x = a; x <= W; x += x & -x){
      for (ll y = b; y <= H; y += y & -y) {
        bit[x][y] += w;
      }
    }
    return;
  }  
  // 閉区間[1,a], [1,b]までの和
  ll sum(ll a, ll b) {
    if(a<=0 or b<=0) return 0;
    ll ret = 0;
    for (ll x = a; x > 0; x -= x & -x) {
      for (ll y = b; y > 0; y -= y & -y) {
        ret += bit[x][y];
      }
    }
    return ret;
  }
  // 閉区間
  ll range_sum(ll x1, ll y1, ll x2, ll y2){
    ll a = sum(x2,y2);
    ll b = sum(x1-1,y2);
    ll c = sum(x2,y1-1);
    ll d = sum(x1-1,y1-1);
    return a-b-c+d;
  }
};

verified