2次元累積和クラスを作成 (二次元累積和)

ライブラリ 累積和

動機

  • 1次元累積和クラスはよく使っているため
  • 2次元累積和を使う問題と出会ったため

Code

// 2次元累積和
struct AccSum2D{
    VV Ac; // accumulate
    ll W;
    ll H;
    AccSum2D(){}
    AccSum2D(VV &A){
      H = A.size();
      W = A[0].size();
      Ac.resize(H+1, VI(W+1));
      // indexを1つずらしてコピー
      rep(i, H){
        rep(j, W){
          Ac[i+1][j+1] = A[i][j];
        }
      }
      // 横に累積
      rep(i, H+1){
        rep(j, W){
          Ac[i][j+1] += Ac[i][j];
        }
      }
      // 縦に累積
      rep(x, W+1){
        rep(y, H){
          Ac[y+1][x] += Ac[y][x];
        }
      }
    }
    // 入力したAの0-indexで指定 (閉区間)
    // sum of (a,b) to (c,d)
    // a, cはy方向
    // b, dはx方向
    ll sum(ll a, ll b, ll c, ll d){
      // 内部ではindexが1ずれる
      a++; b++; c++; d++;
      return Ac[c][d] - Ac[a-1][d] - Ac[c][b-1] + Ac[a-1][b-1];
    }
};

verified

tute san ver

3次元 三次元 累積和