C++: 2D/3D Accumulator Class

C++: 2次元・3次元の累積和を求めるクラス

あるリストの特定区間の総和を繰り返し求める必要がある場合、更新が多いケースでは Binary Indexed Tree(BIT) が有効だ。
http://mogproject.blogspot.jp/2012/02/binary-indexed-tree-bit-in-c.html

ただし、更新は一度だけであとは参照するだけといった場合、単純な累積和テーブルを持たせれば計算量 Θ(1) で計算可能である。
これは、以下のように 2次元・3次元のリストにも適用できる。

区間の総和を求めるには、Inclusion–exclusion principle を利用する。
http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle

・コード

template <typename T=int> class Acum2D {
public:
  Acum2D(int x, int y) {
    data_ = std::vector<std::vector<T> >(x + 1, std::vector<T>(y + 1, 0));
  }
  // must set values in ascending order
  void Set(int x, int y, T value) {
    data_[x + 1][y + 1] =
        value + data_[x][y + 1] + data_[x + 1][y] - data_[x][y];
  }
  // get the sum of data[x][y] such that:
  //     min_x <= x <= max_x and min_y <= y <= max_y
  T Get(int min_x, int min_y, int max_x, int max_y) const {
    if (min_x > max_x || min_y > max_y) return 0;
    ++max_x; ++max_y;
    return data_[max_x][max_y]-
        data_[min_x][max_y] - data_[max_x][min_y] + data_[min_x][min_y];
  }
private:
  std::vector<std::vector<T> > data_;
};

template <typename T=int> class Acum3D {
public:
  Acum3D(int x, int y, int z) {
    data_ = std::vector<std::vector<std::vector<T> > >(x + 1,
        std::vector<std::vector<T> >(y + 1, std::vector<T>(z + 1, 0)));
  }
  // must set values in ascending order
  void Set(int x, int y, int z, T value) {
    data_[x + 1][y + 1][z + 1] = value + data_[x][y + 1][z + 1] +
        data_[x + 1][y][z + 1] + data_[x + 1][y + 1][z] - data_[x][y][z + 1] -
        data_[x + 1][y][z] - data_[x][y + 1][z] + data_[x][y][z];
  }
  // get the sum of data[x][y][z] such that:
  //     min_x <= x <= max_x and min_y <= y <= max_y and min_z <= z <= max_z
  T Get(int min_x, int min_y, int min_z,
      int max_x, int max_y, int max_z) const {
    if (min_x > max_x || min_y > max_y || min_z > max_z) return 0;
    ++max_x; ++max_y; ++max_z;
    return data_[max_x][max_y][max_z] - data_[min_x][max_y][max_z] -
        data_[max_x][min_y][max_z] - data_[max_x][max_y][min_z] +
        data_[min_x][min_y][max_z] + data_[max_x][min_y][min_z] +
        data_[min_x][max_y][min_z] - data_[min_x][min_y][min_z];
  }
private:
  std::vector<std::vector<std::vector<T> > > data_;
};

・使用例

int data2d[5][3] = {{0, 1, 2}, {10, 11, 12}, {20, 21, 22}, {30, 31, 32}, {40, 41, 42}};
Acum2D<> acum2d(5, 3);
for (int i = 0; i < 5; ++i) for (int j = 0; j < 3; ++j) {
  acum2d.Set(i, j, data2d[i][j]);
}
// data[2][1] + data[2][2] + data[3][1] + data[3][2] + data[4][1] + data[4][2]
// = 21 + 22 + 31 + 32 + 41 + 42 = 189
std::cout << acum2d.Get(2, 1, 4, 2) << std::endl;

double data3d[3][3][3] = {
    {{ 0.0,  0.1,  0.2}, { 1.0,  1.1,  1.2}, { 2.0,  2.1,  2.2}},
    {{10.0, 10.1, 10.2}, {11.0, 11.1, 11.2}, {12.0, 12.1, 12.2}},
    {{20.0, 20.1, 20.2}, {21.0, 21.1, 21.2}, {22.0, 22.1, 22.2}},
};
Acum3D<double> acum3d(3, 3, 3);
for (int i = 0; i < 3; ++i) for (int j = 0; j < 3; ++j) for (int k = 0; k < 3; ++k){
  acum3d.Set(i, j, k, data3d[i][j][k]);
}
// data[0][1][2] + data[0][2][2] + data[1][1][2] + data[1][2][2]
// = 1.2 + 2.2 + 11.2 + 12.2 = 26.8
std::cout << acum3d.Get(0, 1, 2, 1, 2, 2) << std::endl;