perogram

2次元BITクラス

参考

Code

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<ll>;
using VV = vector<VI>;

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,b) FOR(i, 0, b)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<'\n'
#define pn(s) cout << (#s) << " " << (s) << '\n'

const ll mod = 1e9 + 7;
const ll inf = 1e18;

struct BIT2D{
  VV bit;
  ll W;
  ll H;
  void resize(ll w, ll h){
    W = w;
    H = h;
    bit.resize(H+10, VI(W+10));
  }
  void add(ll a, ll b, ll w) {
    for (ll x = a; x <= W; x += x & -x){
      for (ll y = b; y <= H; y += y & -y) {
        bit[x][y] += w;
      }
    }
  }  
  ll sum(ll a, ll b) {
    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;
  }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // 動作確認
    auto bit2d = BIT2D();
    bit2d.resize(10, 5);

    bit2d.add(6, 1, 3);
    bit2d.add(2, 4, 7);
    bit2d.add(4, 2, 5);

    pn(bit2d.sum(7, 1));
    pn(bit2d.sum(4, 4));
    pn(bit2d.sum(0, 0));
    pn(bit2d.sum(10, 2));

    return 0;
}

出力

bit2d.sum(7, 1) 3
bit2d.sum(4, 4) 12
bit2d.sum(0, 0) 0
bit2d.sum(10, 2) 8

verified

  • なし
  • これを使う問題と出会った時に・・・
  • 計算量は共にO(logW x logH)

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?